使用深搜，根據(jù)每個(gè)結(jié)點(diǎn)的結(jié)束訪問時(shí)間的降序?qū)Y(jié)點(diǎn)進(jìn)行拓?fù)渑判颍绻谀硞€(gè)結(jié)點(diǎn)的擴(kuò)展過程中發(fā)現(xiàn)反向邊，則出現(xiàn)了矛盾；否則對(duì)所得到的結(jié)點(diǎn)序列，進(jìn)行一次遍歷，對(duì)于相鄰的結(jié)點(diǎn)檢測(cè)是否存在連接邊（存在則表示它們的順序已經(jīng)可以確定），如果所有的相鄰結(jié)點(diǎn)都可確定順序，則這個(gè)序列是完全有序的，對(duì)于后面的輸入可以忽略；如果處理完所有的輸入還不能得到完全有序序列，則輸出序列順序不能確定。
題意實(shí)際上暗示了對(duì)每一次輸入都要做處理，如果對(duì)于某一次輸入已經(jīng)能確定序列矛盾或者序列完全有序，則可以忽略后面的輸入。
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