本文共 3037 字，大约阅读时间需要 10 分钟。
时间限制: 1 Sec 内存限制: 32 MB
一个由不同的值组成的按升序排序的序列，通常使用小于操作符，把元素从小到大排列。
例如，有序序列A，B，C，D表示A<B，B<C和C<D。 现给你一组形如A<B的关系，请你确定是否已经形成一个排序的序列。输入包含多组测试数据。每组输入的第一行是两个正整数n和m。
n表示排序对象的个数，2<=n<=26。排序对象是字母表开始的n个大写字符。 m表示形如A<B的关系的个数。 接下来m行，每行输入一个关系，由三个字符构成：第一个大写字母，符号“<”，第二个大写字母。字母不会超过字母表开始的n个字母的范围。 当n=m=0时，输入结束。对于每组输入，输出一行。该行将是以下三者之一：
Sorted sequence determined after xxx relations: yyy...y.（在xxx个关系后，确定了排序序列：yyy...y） Sorted sequence cannot be determined.（不能确定排序序列） Inconsistency found after xxx relations.（在xxx个关系后，发现关系矛盾） 解释说明： xxx是处理关系时，确定排序序列已经形成或发现关系矛盾时的关系数目，哪种情况先出现，就输出哪种。yyy...y是排序的升序序列。4 6A
Sorted sequence determined after 4 relations: ABCD.Inconsistency found after 2 relations.Sorted sequence cannot be determined.
徐不可说：拓扑排序了解一下！运用拓扑排序的数据结构 判断所给数据满足输出哪种的情况，输入数据给到何时就能够判断出满足的情况。
#include#include #include using namespace std; int N, M; const int MAXN = 27, MAXM = 1000; int g[MAXN][MAXN], in[MAXN], ans[MAXN]; int topoSort() { int in1[MAXN]; for(int i = 0; i < N; i++)//定义一个变量数组 { in1[i] = in[i]; } for(int k = 0; k < N; k++) //遍历所有字母 { int i = 0; while(in1[i]!=0) { i++; if(i >= N) //所有的点都有入度，代表它成环 return 2; //成环，矛盾 } ans[k] = i; //入度为0的点 ，放在r里 in1[i]--; //初值为-1 for(int j = 0; j < N; j++) //把他能到达的点的入度全都-1 if(g[i][j]) in1[j]--; } for(int i = 0; i < N-1; i++) //判断连通性 { int ok = 0; if(g[ans[i]][ans[i+1]]) ok = 1; if(!ok) return 1; //不能确定排列序列 } return 0; //确定排序 } int main() { while(scanf("%d%d", &N, &M)!=EOF && !(!N&&!M)) { memset(g, 0, sizeof(g)); memset(in, 0, sizeof(in)); char s[10]; int next = 0; for(int i = 0; i < M; i++) { scanf("%s", s); if(next) continue; int u = s[0] - 'A', v = s[2] - 'A'; //减去A的值作为编号 g[u][v] = 1; //标记连通 in[v]++; //后面的入度+1 int r = topoSort(); if(r == 0) { printf("Sorted sequence determined after %d relations: ", i+1); for(int j = 0; j < N; j++) { printf("%c", ans[j]+'A'); } printf(".\n"); next = 1; continue; } else if(r == 1 && i == M-1) printf("Sorted sequence cannot be determined.\n"); else if(r == 2) { printf("Inconsistency found after %d relations.\n", i+1); next = 1; continue; } } } return 0; }
转载地址：http://extgn.baihongyu.com/