好贷网好贷款

toj2892Task 拓扑排序——模板

发布时间:2016-12-4 3:47:48 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"toj2892Task 拓扑排序——模板",主要涉及到toj2892Task 拓扑排序——模板方面的内容,对于toj2892Task 拓扑排序——模板感兴趣的同学可以参考一下。

抛弃了百度空间,以后acm的题都往这里发了 toj2892——任务先后顺序问题,看是否一个有向图中有环 //toj2892 #include<iostream> #include<memory.h> using namespace std; int i,j,k,x,y,m,n,into[101]; bool topology(int a[][50]) { memset(into,0,sizeof(into)); for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(a[i][j]!=0)into[j]++;//求出每个点的入度 into[0]=1; for(i=1;i<=n;i++) { j=0; while(into[j]!=0)//找出入度为0的点,即没前驱的那个 { j++; if(j>n)return false;//如果找不到了证明有环 } into[j]=-1;//删除节点j for(k=1;k<=n;k++) { if(a[j][k]>0)//删除所有j节点连着的边 into[k]--; } } return true; } int main() { int t,a[50][50]; cin>>t; while(t--) { cin>>n>>m; memset(a,0,sizeof(a)); for(i=1;i<=m;i++) { cin>>x>>y; a[x][y]=1; } if(topology(a)) cout<<1<<endl; else cout<<0<<endl; } return 0; }

上一篇:砝码 碎片问题
下一篇:剑指offer 五

相关文章

相关评论