#include<stdio.h> #include<string.h> int indegree[101],map[101][101];//indegree[]记录各个节点的入度。 int s[101],top;//栈s[]中存放入度为0的节点。 void tuopu(int n) { int i,j,top=0,t,count=0; memset(s,0,sizeof(s)); for(i=0;i<n;i++) { if(0==indegree[i]) { s[top++]=i; } } while(top>0) { t=s[top-1]; top--; count++; for(j=0;j<n;j++) { if(map[t][j]) { indegree[j]--; if(0==indegree[j]) { s[top++]=j; } } } } if(count<n) printf("NO\n");//count小于n说明存在环 else printf("YES\n"); } int main() { int n,m,i,j,a,b; while(scanf("%d%d",&n,&m)&&n&&m) { memset(map,0,sizeof(map)); memset(indegree,0,sizeof(indegree)); for(i=0;i<m;i++) { scanf("%d%d",&a,&b); if(!map[a][b]) { map[a][b]=1; indegree[b]++; } } tuopu(n); } return 0; }
hdu 3342 Legal or Not,布布扣,bubuko.com
原文:http://www.cnblogs.com/duan-to-success/p/3851925.html