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.\n",i); 103 } 104 } 105 if(i == m && !flag) 106 printf("Sorted sequence cannot be determined.\n"); 107 } 108 } 109 }View Code