2345. [图论基础与应用-第二章]将所有元素排序

由一些不同元素组成的升序序列可以用若干个小于号将所有的元素按从小到大的顺序排列起来。例如,排序后的序列为A, B, C, D,这意味着A<B、B<C和C<D。在本题中,给定一组形如A < B的关系式,试判定是否存在一个有序序列。

输入

输入文件包含多个测试数据。每个测试数据的第1行为两个正整数n和m,n为要排序的元素个数(2≤n≤26),这n个元素为字母表前n个大写字母,m表示有m个形如A<B的关系式。接下来有m行,每行描述了一个关系式,包含一个大写字母、字符“<”、另一个大写字母;这些字母均不会超出字母表前n个字母。n = m = 0表示输入结束。

输出

对每个测试数据,输出一行,内容为以下3行之一。 Sorted sequence determined after xxx relations: yyy…y. Sorted sequence cannot be determined. Inconsistency found after xxx relations. 其中“xxx”为判定出有序序列存在或存在矛盾(inconsistency)时已经处理的关系式数目,哪一种情形最先出现,则按哪一种情形处理,“yyy…y”为排序后的升序序列。

样例

标准输入 复制文本
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.
登录以提交代码。
单点时限 1 秒
内存限制 256 MB
提交 0
通过 0