使用深搜，根據(jù)每個結點的結束訪問時間的降序對結點進行拓撲排序，如果在某個結點的擴展過程中發(fā)現(xiàn)反向邊，則出現(xiàn)了矛盾；否則對所得到的結點序列，進行一次遍歷，對于相鄰的結點檢測是否存在連接邊（存在則表示它們的順序已經可以確定），如果所有的相鄰結點都可確定順序，則這個序列是完全有序的，對于后面的輸入可以忽略；如果處理完所有的輸入還不能得到完全有序序列，則輸出序列順序不能確定。
題意實際上暗示了對每一次輸入都要做處理，如果對于某一次輸入已經能確定序列矛盾或者序列完全有序，則可以忽略后面的輸入。
1 #include<stdio.h>
2 #include<string.h>
3 int n,m;
4 int e[27][27];
5 char in[4];
6 char temp[27];
7 int cur;
8 int incons;
9 int color[27];
10 void dfs(int k)
11 {
12 color[k]=1;
13 int i;
14 for(i=1;i<=n;++i)
15 {
16 if(e[k][i]&&color[i]==0) dfs(i);
17 else if(e[k][i]&&color[i]==1) incons=1; //reverse edge exist, inconsistency found
18 }
19 color[k]=2;
20 temp[cur++]=k-1+'A';
21 }
22 int main()
23 {
24 int i,j,found;
25 while(scanf("%d%d",&n,&m)&&n&&m)
26 {
27 memset(e,0,sizeof(e));
28 found=0;
29 incons=0;
30 for(i=1;i<=m;++i)
31 {
32 scanf("%s",in);
33 e[in[0]-'A'+1][in[2]-'A'+1]=1;
34 if(!found&&!incons)
35 {
36 cur=0;
37 memset(color,0,sizeof(color));
38 for(j=1;j<=n;++j)
39 if(color[j]==0) dfs(j);
40 temp[cur]='\0';
41 if(incons==1) //inconsistency found
42 incons=i;
43 else{
44 int bb=1;
45 for(j=cur-1;j>0;--j) //check if the sort of sequence can be confirmed
46 if(!e[temp[j]-'A'+1][temp[j-1]-'A'+1]) {bb=0;break;}
47 if(bb) found=i; // sorted sequence determined
48 }
49 }
50 }
51 char tt;
52 for(i=0,j=cur-1;i<j;i++,j--) //reverse the sorted sequence
53 {
54 tt=temp[i];
55 temp[i]=temp[j];
56 temp[j]=tt;
57 }
58 if(incons) printf("Inconsistency found after %d relations.\n",incons);
59 else if(found) printf("Sorted sequence determined after %d relations: %s.\n",found,temp);
60 else printf("Sorted sequence cannot be determined.\n");
61 }
62 return 1;
63 }
64