hihoCoder #1174 : 拓扑排序·一 (判断循环图)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了hihoCoder #1174 : 拓扑排序·一 (判断循环图)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1556字，纯文字阅读大概需要3分钟。
内容图文
| G++ | 261ms | 13MB |
题意：给出n门课程的修读所需要的前置课程的关系，按理说应该是个拓扑图，但是因为某些原因导致了混乱，所以有可能不是一个拓扑图。现在的问题是，判断该图是否为一个拓扑图（即无环图）。
思路：每次删除全部入度为0的结点，一直删下去肯定是没有任何点存在的，如果不是拓扑图的话就必有环，那么肯定有点的入度永远不为0。若到删到最后没有点存在，那么就是correct的。
1 #include<bits/stdc++.h>
2usingnamespace std;
3constint N=100100;
4 5 vector< vector<int> > vect;
6int cnt[N]; //记录每个点的入度 7 8bool cal(int n)
9{
10 vector<int> a;//存放入度为0的点11for(int i=1; i<=n; i++) //先在cnt中找到入度为0的所有点12if(!cnt[i]) a.push_back(i);
13 vector<int> b;//临时存放入度为0的点14while(!a.empty())
15 {
16 b.clear();
17for(int i=0; i<a.size(); i++) //每个入度为0的点x18 {
19for(int j=0; j<vect[a[i]].size(); j++) //每个与x相连的点20 {
21 cnt[vect[a[i]][j]]--;
22if(!cnt[vect[a[i]][j]])//只有那些有变化的点才可能入度为0。23 b.push_back(vect[a[i]][j]);
24 }
25 vect[a[i]].clear();
26 }
27 a.clear();
28if(!b.empty()) a.insert(a.end(), b.begin(), b.end());
29 }
30for(int i=1; i<=vect.size(); i++)
31 {
32if(cnt[i]>0)
33returnfalse;
34 }
35returntrue;
36}
3738void init(int n) //初始化用的39{
40 memset(cnt,0,sizeof(cnt));
41 vect.clear();
42 vector<int> tmp;
43for(int i=0; i<=n; i++)
44 vect.push_back(tmp);
45}
46int main()
47{
48//freopen("e://input.txt","r",stdin);49int t, n, m, a, b;
50 cin>>t;
51while(t--)
52 {
53 scanf("%d%d",&n,&m);
54 init(n);
55for(int i=0; i<m; i++)
56 {
57 scanf("%d%d",&a,&b);
58 vect[a].push_back(b);
59 cnt[b]++;
60 }
61if(cal(n))
62 printf("Correct\n");
63else64 printf("Wrong\n");
65 }
66return0;
67 }
hihoCoder #1174 : 拓扑排序·一 (判断循环图)
原文：http://www.cnblogs.com/xcw0754/p/4544347.html
内容总结
以上是互联网集市为您收集整理的hihoCoder #1174 : 拓扑排序·一 (判断循环图)全部内容，希望文章能够帮你解决hihoCoder #1174 : 拓扑排序·一 (判断循环图)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。