- // 拓扑排序判断是否有环
- #include<cstdio>
- #include<algorithm>
- #include<string.h>
- #include<math.h>
- #include<queue>
- using namespace std;
- typedef long long ll;
- const int maxn=1e2+10;
- int G[maxn][maxn];
- int in[maxn];
- void init()
- {
- memset(G,0,sizeof(G)); // 图
- memset(in,0,sizeof(in)); // 入度
- }
- int Toposort(int n)
- {
- int aim;
- int cot=0;
- int flag=1; //1 的时候表示有序
- // 每一次循环, 找出入度为 0 的点, 如果找不到就证明有环 (这点强行记忆)
- // 找到之后, 将这个点所连的边的另一个端点入度 - 1;
- // 算法结束
- for(int i=1;i<=n;i++){
- int num=0;
- for(int j=1;j<=n;j++)
- if(!in[j]){
- num++;
- aim=j;
- break;
- }
- if(!num) return 0; // 有环;
- in[aim]=-1;
- for(int j=1;j<=n;j++)
- if(G[aim][j]) in[j]--;
- }
- return flag;
- }
- int main()
- {
- int n,m;
- while(scanf("%d%d",&n,&m)!=EOF){
- init(); // 初始化
- for(int i=1;i<=m;i++){
- int u,v;
- scanf("%d%d",&u,&v);
- G[u][v]=1;
- in[v]++; //u 到 v 有边 所以 v 的入度 ++;
- }
- int flag=Toposort(n);
- if(flag==1) printf("YES\n");
- else printf("NO\n");
- }
- return 0;
- }
- .
来源: http://www.bubuko.com/infodetail-3282357.html