Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3151 Accepted Submission(s): 1432
在一个群里面，大家互相请教问题，比如A请教B，我们就把B叫做师傅，把A叫做徒弟，这样会产生很多“师傅——徒弟”的关系，一个徒弟可以有很多的师傅，一个师傅也可以有很多徒弟，这是合法的，但是不能出现A是B的师傅而且B是A的师傅，或者A是B的徒弟而且B是A的徒弟，或者在一个更大的关系环里面出现这种情况。
很明显题目的意思就是，判断一个给定的有向图中是否存在环。了解了这些，解题方法就非常简单了，那就是直接进行拓扑排序即可，统计拓扑排序完成之时能记录的度为0的节点的个数，若个数等于节点个数则说明无环，否则是有环的。
该题为输入多组数据，所以我们每一次进行询问和查询的时候都要将所有的数组以及sum，tot等记录的值清空。
#include<queue> #include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define N 1000 using namespace std; int n,m,a,b,x,sum,tot; int head[N],in[N]; queue<int>q; struct Edge { int from,to,next; }edge[N]; void add(int x,int y) { tot++; edge[tot].to=y; edge[tot].next=head[x]; head[x]=tot; } int main() { while(scanf("%d%d",&n,&m)) { while(!q.empty()) q.pop(); tot=0,sum=0; memset(in,0,sizeof(in)); memset(head,0,sizeof(head)); if(n==0) return 0; for(int i=1;i<=m;i++) scanf("%d%d",&a,&b),add(a,b),in[b]++; for(int i=0;i<n;i++) if(in[i]==0) q.push(i); while(!q.empty()) { x=q.front();q.pop();sum++; for(int i=head[x];i;i=edge[i].next) { in[edge[i].to]--; if(in[edge[i].to]==0) q.push(edge[i].to); } } if(sum!=n) printf("NO\n"); else printf("YES\n"); } }
原文：http://www.cnblogs.com/z360/p/6978846.html