題目大意：
對于給定的前n個字母( A-... )，給出可能的字母間的偏序，問是否能確定構(gòu)成一個線性序T，如果能或不能，則給出最早能做出判斷的偏序在第幾個。否則說明不可判。
這道題有點犀利，弄了半個晚上。一開始思維沒打開，找不到思路，最后想到判斷可達(dá)性的復(fù)雜度不可能比DFS傳遞閉包更好，因此果斷改變思路?？梢皂樞蜃x入每個偏序，對于每次讀入，構(gòu)造一次拓?fù)渑判?，那么在第幾個偏序出解，結(jié)果就在第幾。
注意容易出現(xiàn)的邏輯錯誤，首先就是“判斷是否能構(gòu)成T序”的優(yōu)先級高于T是否唯一，也就是說當(dāng)出現(xiàn)多個可隨意次序的點時，不能馬上輸出不唯一，需要將拓?fù)渑判蜃鐾暌员ＷC沒有成環(huán)，判環(huán)優(yōu)先級更高。
算法可以順序讀入偏序，隨之做拓?fù)洳疬?，?dāng)遇到棧尺寸大于1（多個不可比），不可比標(biāo)記置一。拓?fù)浣Y(jié)束后，若成環(huán)，則輸出成環(huán)，否則輸出T唯一或繼續(xù)讀入偏序（當(dāng)前不唯一）。若始終不成環(huán)且不唯一，最終結(jié)果自然不唯一。
4 4
A<B
C<B
D<B
B<A
Inconsistency found after 4 relations.
1
#include<cstdio>
2#include<cstdlib>
3#include<cstring>
4#include<stack>
5using namespace std;
6int g[26][26],degree[26],degreeR[26],path[26];
7bool ring,more;
8int n,m;
9
int main()
{
10
int i,j,k,t;
11 char u,v;
12 int ele;
13 bool sure,unsure;
14
while(scanf("%d%d",&n,&m),n|m){
15 memset(g,0,sizeof(g));
16 memset(degreeR,0,sizeof(degreeR));
17 sure = false;
18 for(getchar(),i=0;i<m;i++){
19 scanf("%c<%c",&u,&v);getchar();
20
21 g[ u-'A' ][ v-'A' ]=1;
22 degreeR[ v-'A' ]++;
23 stack<int> _sta;
24 for(j=0;j<n;j++) if( degreeR[j] == 0 ) _sta.push(j);
25
26 for(j=0;j<n;j++) degree[j]=degreeR[j];
27 more=false;
28 ring=false;
29 for(j=0;j<n;j++){
30 if( _sta.size()>1 ) more=true; // unsure
31 if( _sta.empty() ){ ring=true; break; } // ring
32 ele = _sta.top(); _sta.pop();
33 path[j]=ele;
34 for(k=0;k<n;k++){
35 if( g[ele][k]!=0 && --degree[k] == 0 ) { _sta.push(k); }
36
}
37 }
38
39 if( j == n && more == false){
40 printf("Sorted sequence determined after %d relations: ",i+1);
41 for(j=0;j<n;j++) printf("%c",'A'+path[j]); printf(".\n");
42 sure=true;
43 break;
44 }
45 else if( ring == true ){ printf("Inconsistency found after %d relations.\n",i+1); sure=true; break; }
46 }
47 if( sure == false ) printf("Sorted sequence cannot be determined.\n");
48 for(t=i+1;t<m;t++){ scanf("%c<%c",&u,&v); getchar(); }
49 }
50 return 0;
51
}
52