拓扑排序,判断是否可准确排序,或者存在环,或者无法准确排序
#include<stdio.h> #include<string.h> int n,m,cnt=1,in[30],g[30][30],tt[30]; char final[30]; int topo() { int i,j,hash,done=0,num=0; int vis[30]; memset(vis,0,sizeof(vis)); final[n]='\0'; while(1) { hash=0; for(i=1;i<=n;i++) { if(!vis[i]&&!in[i]) if(!hash) { vis[i]=1; hash=i; final[n-num-1]=i+'A'-1; num++; } else {done=1;break;} } if(num==n) { if(done) return -1; return 1; } if(!hash) return 2; if(hash) { for(j=1;j<=n;j++) { if(g[hash][j]) in[j]-=g[hash][j]; } } } } main() { int i,ok,sign; char s[10]; //freopen("D:\\o.txt","r",stdin); while(scanf("%d%d",&n,&m)&&n+m) { sign=0; memset(tt,0,sizeof(tt)); memset(g,0,sizeof(g)); getchar(); for(i=1;i<=m;i++) { gets(s); tt[s[0]-'A'+1]++; g[s[2]-'A'+1][s[0]-'A'+1]++; if(!sign) { memcpy(in,tt,sizeof(in)); ok=topo(); if(ok==1) { sign=1; printf("Sorted sequence determined after %d relations: %s.\n",i,final); } else if(ok==2) { sign=1; printf("Inconsistency found after %d relations.\n",i); } else if(ok==-1&&m==i) { sign=1; printf("Sorted sequence cannot be determined.\n"); } } } } return 0; }