#include <stdio.h> #include <string.h> int map[28][28],num,n; char output[28]; int Floyd() { int i,k,j; for(i=1;i<=n;i++) for(k=1;k<=n;k++) for(j=1;j<=n;j++) if( map[k][i] && map[i][j] ) map[k][j]=1; for(i=1;i<=n;i++) if(map[i][i]==1) return 1; return 0; } int Topsort() { int cou,ind,k,i,degree[28],used[28]; num =0; memset(used,0,sizeof(used)); memset( degree,0,sizeof(degree) ); for(i=1;i<=n;i++) for(k=1;k<=n;k++) if(map[i][k]) degree[k]++; for(i=1;i<=n;i++) { cou=0; for(k=1;k<=n;k++) if(degree[k]==0 && !used[k]) { output[num++]=k+‘A‘-1; used[k]=1; cou++; ind=k; } if(cou>1) return 0; for(k=1;k<=n;k++) if(map[ind][k]) degree[k]--; } output[num]=‘\0‘; return 2; } int main() { int m,flag,i,pos; char str[4]; while( scanf("%d%d",&n,&m)!=EOF && ( n || m ) ) { flag=0; memset(map,0,sizeof(map)); for(i=1;i<=m;i++) //每输入一条边就进行拓扑排序和判断有没有环 { scanf("%s",str); map[str[0]-‘A‘+1][str[2]-‘A‘+1] = 1; if(flag) continue; flag=Floyd(); if(flag==1) pos=i; else if(flag==0) flag=Topsort(); else continue; if(flag==2) pos=i; } if(flag==2) printf("Sorted sequence determined after %d relations: %s.\n",pos,output); else if(flag==1) printf("Inconsistency found after %d relations.\n",pos); else printf("Sorted sequence cannot be determined.\n"); } return 0; }
Sorting It All Out(拓扑排序,floyd)
原文:http://www.cnblogs.com/You-Change/p/3517279.html