C++-POJ1094-Sorting It All Out[拓扑排序][邻接矩阵]

 1 #include<cstdio>
 2 #include<cstring>
 3 int map[27][27],indegree[27],q[27];
 4 int TopoSort(int n){
 5     int t=0,temp[27],p,m,flag=1;  //flag=1:有序 flag=-1:不确定
 6     for(int i=1;i<=n;i++)temp[i]=indegree[i];
 7     for(int i=1;i<=n;i++){
 8         m=0;for(int j=1;j<=n;j++)if(temp[j]==0)m++,p=j;//查找入度为零的顶点个数
 9         if(m==0)return 0; //有环
10         if(m>1) flag=-1;  //无序
11         q[++t]=p,temp[p]=-1;//入度为零的点入队
12         for(int j=1;j<=n;j++)if(map[p][j]==1)temp[j]--;
13     }
14     return flag;
15 }
16 int main(){
17     int n,m,sign,x,y;
18     for(char s[5];scanf("%d%d",&n,&m)!=EOF;){
19         if(n==0&&m==0)break;
20         memset(map,0,sizeof(map)),sign=0;
21         memset(indegree,0,sizeof(indegree));
22         for(int i=1;i<=m;i++){
23             scanf("%s",s);
24             if(sign)continue;
25             x=s[0]-'A'+1,y=s[2]-'A'+1;
26             map[x][y]=1,indegree[y]++;
27             int f=TopoSort(n);
28             if(f==0)sign=1,printf("Inconsistency found after %d relations.
",i);
29             if(f==1){
30                 sign=1,printf("Sorted sequence determined after %d relations: ",i);
31                 for(int j=1;j<=n;j++)printf("%c",q[j]+'A'-1);
32                 puts(".");
33             }
34         }
35         if(!sign)puts("Sorted sequence cannot be determined.");
36     }
37     return 0;
38 }