使用深搜，根据每个结点的结束访问时间的降序对结点进行拓扑排序，如果在某个结点的扩展过程中发现反向边，则出现了矛盾；否则对所得到的结点序列，进行一次遍历，对于相邻的结点检测是否存在连接边（存在则表示它们的顺序已经可以确定），如果所有的相邻结点都可确定顺序，则这个序列是完全有序的，对于后面的输入可以忽略；如果处理完所有的输入还不能得到完全有序序列，则输出序列顺序不能确定。
题意实际上暗示了对每一次输入都要做处理，如果对于某一次输入已经能确定序列矛盾或者序列完全有序，则可以忽略后面的输入。
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