前置知识：拓扑排序
详细注释都在代码里
1 //该题题意明确，就是给定一组字母的大小关系判断他们是否能组成唯一的拓扑序列。 2 //是典型的拓扑排序，但输出格式上确有三种形式： 3 4 // 1.该字母序列有序，并依次输出； 5 6 // 2.该序列不能判断是否有序； 7 8 // 3.该序列字母次序之间有矛盾，即有环存在。 9 10 // 而这三种形式的判断是有顺序的：先判断是否有环（3）， 11 //再判断是否有序（1），最后才能判断是否能得出结果（2）。 12 //注意：对于（2）必须遍历完整个图，而（1）和（3）一旦得出结果， 13 //对后面的输入就不用做处理了。 14 15 //有一个问题，我不太清楚，就是在确定有序之后，就直接输出答案， 16 //对右面的输入也不再处理，但是后面的输入可以让其成为环的话又就会 17 //让其成为环，所以我想这道题就是在确定有序之后，后面的数据，就都不要了。 18 //应该是这意思把 19 #include<cstdio> 20 #include<algorithm> 21 #include<string.h> 22 #include<math.h> 23 #include<queue> 24 using namespace std; 25 typedef long long ll; 26 const int maxn=1e2+10; 27 int G[30][30]; 28 int in[30]; 29 int q[30]; 30 void init() 31 { 32 memset(G,0,sizeof(G)); //图 33 memset(in,0,sizeof(in)); //入度 34 } 35 int Toposort(int n) 36 { 37 int aim;int cot=0; 38 int tmpin[30]; 39 int flag=1; //1的时候表示有序 40 for(int i=1;i<=n;i++) tmpin[i]=in[i]; //将入度复制到tmpin里面来 41 for(int i=1;i<=n;i++){ 42 int num=0; 43 for(int j=1;j<=n;j++) 44 if(!tmpin[j]) num++,aim=j; //这里来判断入度数量，aim是入度为0的那个点 45 //这里如果出现多个入度，就会选择最后面那个先进行操作； 46 if(!num) return 0; //有环； 47 if(num>1) flag=-1; //无序 48 q[cot++]=aim; 49 tmpin[aim]=-1; 50 for(int j=1;j<=n;j++) 51 if(G[aim][j]) tmpin[j]--; 52 } 53 return flag; 54 55 } 56 int main() 57 { 58 int n,m; 59 while(scanf("%d%d",&n,&m)!=EOF){ 60 if(!n&&!m) break; 61 init(); 62 char str[5]; 63 int flag=0; 64 for(int i=1;i<=m;i++){ 65 scanf("%s",str); 66 if(flag) continue; 67 int l=str[0]-'A'+1; 68 int r=str[2]-'A'+1; 69 G[l][r]=1; 70 in[r]++; 71 int judge=Toposort(n); 72 //有环 73 if(!judge) printf("Inconsistency found after %d relations.\n",i),flag=1; 74 if(judge==1){ //有序 75 printf("Sorted sequence determined after %d relations: ",i); 76 for(int j=0;j<n;j++) 77 printf("%c",q[j]+'A'-1); 78 printf(".\n"); 79 flag=1; 80 } 81 } 82 //无序 83 if(!flag) printf("Sorted sequence cannot be determined.\n"); 84 } 85 return 0; 86 }