题意

输入n, m，前者表示有多少个大写英文字母（从A开始），后者表示下面有多少个大小关系式子，然后根据给定的大小关系式子判断是否能得出他们的大小关系。若能求出，则说明从第几条式子起就已经可以确定关系；若存在矛盾，则说明从第几条式子起存在矛盾；若不能求出则直接说明。

样例输入

4 6

A<B

A<C

B<C

C<D

B<D

A<B

3 2

A<B

B<A

26 1

A<Z

0 0

样例输出

Sorted sequence determined after 4 relations: ABCD.

Inconsistency found after 2 relations.

Sorted sequence cannot be determined.

思路

题目重点在于要求出经过多少个式子后就能得出结论。因此，每读入一个式子就应进行一次拓扑排序。

在拓扑排序的循环中，若每次循环只有一个入度为0的点，则说明大小关系已确定；否则说明大小关系无法确定。若拓扑排序，则说明存在回路，即大小关系存在矛盾。

注意点

先判断是否存在矛盾，再判断是否确定关系，最后才判断是否不能确定关系。

举个例子

6 6

A<F

B<D

C<E

F<D

D<E

E<F

output：

Inconsistency found after 6 relations.

矛盾和多选同时存在时，优先判断是否矛盾

5 5

A<B

B<C

C<D

D<E

E<A

output:

Sorted sequence determined after 4 relations: ABCDE

在矛盾之前如果有成功的，算是成功

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6 const int N = 26, M = 10000; 7 int u[M], v[M], Next[M], first[N], in[N]; 8 bool TPSort(int n, int m, int time) 9 {10     int topo[N], tempin[N];11     memcpy(tempin, in, sizeof(tempin));12     queue
         
           q;13     for(int i=0; i
          
            1 ? true : false;17 int num, x;18 for(num = 0; !q.empty(); ++num)19 {20 x = q.front();21 q.pop();22 for(int temp = first[x]; ~temp; temp = Next[temp])23 if(!--tempin[v[temp]])24 q.push(v[temp]);25 if(!ok)26 ok = q.size() > 1 ? true : false;27 topo[num] = x;28 }29 if(num - n) //有环30 {31 printf("Inconsistency found after %d relations.\n", time+1);32 return true;33 }34 else35 {36 if(ok)37 return false;38 printf("Sorted sequence determined after %d relations: ", time+1);39 for(int i=0; i
          
         
        
       
      
     

测试数据：

4 6A
      
       
        
         
          
         
        
       
      

Sorted sequence determined after 4 relations: ABCD.Inconsistency found after 2 relations.Sorted sequence cannot be determined.Sorted sequence determined after 4 relations: ABCDE.Inconsistency found after 6 relations.Sorted sequence determined after 6 relations: DCAB.Sorted sequence determined after 29 relations: CFDAEBHGJI.Sorted sequence cannot be determined.Inconsistency found after 48 relations.Sorted sequence determined after 318 relations: GMNVKCHFOBRJDZLPXAYSEIWQTU.Sorted sequence determined after 25 relations: ABCDEFGHIJKLMNOPQRSTUVWXYZ.Sorted sequence determined after 7 relations: BADCE.Sorted sequence determined after 158 relations: HNAMGIPCTBJFRLEODKSQ.Inconsistency found after 35 relations.Sorted sequence cannot be determined.Sorted sequence determined after 7 relations: ABDEC.Sorted sequence cannot be determined.Sorted sequence determined after 11 relations: ACDBFE.Sorted sequence cannot be determined.Sorted sequence cannot be determined.Sorted sequence determined after 179 relations: CHQNAMDLRFPGISBJOKET.