Sorting It All Out （拓扑排序+floyd）

An ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not.

Input

Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 <= n <= 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character "<" and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input.

Output

For each problem instance, output consists of one line. This line should be one of the following three:

Sorted sequence determined after xxx relations: yyy...y.
Sorted sequence cannot be determined.
Inconsistency found after xxx relations.

where xxx is the number of relations processed at the time either a sorted sequence is determined or an inconsistency is found, whichever comes first, and yyy...y is the sorted, ascending sequence.

Sample Input

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

Sample Output

Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.


题意:n个字母，m个不等式，从1到m个不等式，问到第几个不等式的时候能确定字母间的大小关系，或者会出现矛盾（拓扑环），如果到m个不等式都无法确定，那就是无序的。：：
注：这个从1到m是题目中没有给出的，但是题目确实是判断最少不等式确定有序，或者确定矛盾，如果都无法确定才认为是无序的。

思路：其实主要就是拓扑排序，拓扑排序过程中，如果没有入度为0的点，那么就存在环，就是矛盾的，floyd可有可无。
如果出现多个零点进入队列，那么就是无序的，但是无序优先级最低，所以不能立即退出，需要继续拓扑排序，判断完所有点入度情况，看看是否存在矛盾。
至于加入的floyd，由于floyd可以直接处理传递关系，就可以直接判出是否存在矛盾，然后，如果这时候再出现无序就能直接退出。


（若不使用floyd，代码如注释）

  1 #include<queue>
  2 #include<cstdio>
  3 #include<cstring>
  4 
  5 
  6 using namespace std;
  7 
  8 int n,m;
  9 
 10 int maps[30][30];
 11 struct Node
 12 {
 13     int a,b;
 14     int val;
 15     Node(int a=0,int b=0,int val=0):a(a),b(b),val(val) {}
 16 } node[1000];
 17 
 18 int ans[30];
 19 bool topsort()
 20 {
 21     for(int k=1;k<=n;k++)
 22     {
 23         for(int i=1;i<=n;i++)
 24         {
 25             for(int j=1;j<=n;j++)
 26             {
 27                 maps[i][j] |= maps[i][k] & maps[k][j];
 28             }
 29         }
 30     }
 31     for(int i=1;i<=n;i++)if(maps[i][i])return 1;
 32     return 0;
 33 }
 34 
 35 int check()
 36 {
 37     if(topsort())return -1;
 38     int ind[30];
 39     memset(ind,0,sizeof(ind));
 40     for(int i=1; i<=n; i++)
 41     {
 42         for(int j=1; j<=n; j++)
 43         {
 44             if(maps[i][j])
 45             {
 46                 ind[j]++;
 47             }
 48         }
 49     }
 50     int tot,top,flag=1;
 51     for(int i=1;i<=n;i++)
 52     {
 53         tot = 0;
 54         for(int j=1;j<=n;j++)
 55         {
 56             if(!ind[j])
 57             {
 58                 tot++;
 59                 top = j;
 60             }
 61         }
 62         if(tot >= 2) return 0;
 63 //        if(tot >= 2)flag = 0;
 64 //        if(!tot)return -1;
 65         ans[i] = top;
 66         ind[top] = -1;
 67         for(int i=1;i<=n;i++)
 68         {
 69             if(maps[top][i])ind[i]--;
 70         }
 71     }
 72 //  return flag;
 73     return 1;
 74 }
 75 
 76 int main()
 77 {
 78     while(~scanf("%d%d",&n,&m)&&n&&m)
 79     {
 80         int flag  = 0;
 81         memset(maps,0,sizeof(maps));
 82         char a,b,c;
 83         for(int i=1; i<=m; i++)
 84         {
 85             scanf(" %c %c %c",&a,&b,&c);
 86             if(b == '<')
 87                 maps[a-'A'+1][c-'A'+1] = 1;
 88             else
 89                 maps[c-'A'+1][a-'A'+1] = 1;
 90             if(!flag)
 91             {
 92                 flag = check();
 93                 if(flag == 1)
 94                 {
 95                     printf("Sorted sequence determined after %d relations: ",i);
 96                     for(int j=1; j<=n; j++)
 97                         printf("%c",ans[j]+'A'-1);
 98                     puts(".");
 99                 }
100                 else if(flag == -1)
101                 {
102                     printf("Inconsistency found after %d relations.
",i);
103                 }
104             }
105             if(i == m && !flag)
106                 printf("Sorted sequence cannot be determined.
");
107         }
108     }
109 }

View Code