- #include<cstdio>
- #include<cstring>
- int map[27][27],indegree[27],q[27];
- int TopoSort(int n){
- int t=0,temp[27],p,m,flag=1; //flag=1: 有序 flag=-1: 不确定
- for(int i=1;i<=n;i++)temp[i]=indegree[i];
- for(int i=1;i<=n;i++){
- m=0;for(int j=1;j<=n;j++)if(temp[j]==0)m++,p=j;// 查找入度为零的顶点个数
- if(m==0)return 0; // 有环
- if(m>1) flag=-1; // 无序
- q[++t]=p,temp[p]=-1;// 入度为零的点入队
- for(int j=1;j<=n;j++)if(map[p][j]==1)temp[j]--;
- }
- return flag;
- }
- int main(){
- int n,m,sign,x,y;
- for(char s[5];scanf("%d%d",&n,&m)!=EOF;){
- if(n==0&&m==0)break;
- memset(map,0,sizeof(map)),sign=0;
- memset(indegree,0,sizeof(indegree));
- for(int i=1;i<=m;i++){
- scanf("%s",s);
- if(sign)continue;
- x=s[0]-'A'+1,y=s[2]-'A'+1;
- map[x][y]=1,indegree[y]++;
- int f=TopoSort(n);
- if(f==0)sign=1,printf("Inconsistency found after %d relations.\n",i);
- if(f==1){
- sign=1,printf("Sorted sequence determined after %d relations:",i);
- for(int j=1;j<=n;j++)printf("%c",q[j]+'A'-1);
- puts(".");
- }
- }
- if(!sign)puts("Sorted sequence cannot be determined.");
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3457068.html