Description
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 0Sample Output
Sorted sequence determined after 4 relations: ABCD. Inconsistency found after 2 relations. Sorted sequence cannot be determined.Source
East Central North America 2001
/* 传递闭包和拓扑排序的结合体 用mat数组做传递闭包，如果出现矛盾，即可输出，但要读入所有要读入的数据 用map,in,visit数组做拓扑排序，得出解。这里要注意，由于拓扑序列只有一个解，则每次in[i]数组只有一个为0 如果最后没有答案输出，则没有解 */ #include<cstdio> #include<cstring> int n,m; int map[30][30];//存储拓扑排序的图，不能变 int mat[30][30];//判断矛盾 char s[10]; char str[30]; int in[30],ou[30]; bool f,visit[30]; void tuopu(int depth) { if(depth>=n) { str[depth]=0; f=true; return; } int num=0; int k; for(int i=1;i<=n;i++) if(ou[i]==0&&!visit[i]) { num++; k=i; } if(num>1) return; for(int i=1;i<=n;i++) if(map[k][i]==1) ou[i]--; visit[k]=1; str[depth]='A'+k-1; tuopu(depth+1); } int main() { while(scanf("%d%d",&n,&m)!=EOF) { if(n==0&&m==0) break; if(m<n-1) //构不成连通图，更别说拓扑排序了 { for(int i=1;i<=m;i++) scanf("%s",s); printf("Sorted sequence cannot be determined./n"); continue; } memset(map,0,sizeof(map)); memset(mat,0,sizeof(mat)); memset(in,0,sizeof(in)); f=false; bool flag=true; int x,y; for(int d=1; d<=m; d++) { scanf("%s",s); if(!flag) continue; x=s[0]-'A'+1; y=s[2]-'A'+1; map[x][y]=1; mat[x][y]=1; in[y]++; for(int i=1; i<=n; i++) if(mat[i][x]) mat[i][y]=1; //传递闭包 for(int i=1; i<=n; i++) if(mat[y][i]) mat[x][i]=1; for(int j=1; j<=n&&flag; j++) //检测是否是出矛盾 for(int k=1; k<=n&&flag; k++) if(j!=k&&mat[j][k]==1&&mat[k][j]==1) { printf("Inconsistency found after %d relations. /n",d); flag=false; } if(!flag) continue; for(int i=1;i<=n;i++) ou[i]=in[i]; memset(visit,0,sizeof(visit)); tuopu(0); if(f) { printf("Sorted sequence determined after %d relations: %s./n",d,str); flag=false; } } if(flag) printf("Sorted sequence cannot be determined./n"); } return 0; }
