#zDLlydlt60x6104dc. 排序 Sorting It All Out

排序 Sorting It All Out

好的,这是整理好的完整题目描述,包含输入输出格式、样例及详细解释,适合直接上传平台。


题目描述

给定 nn 个变量,用前 nn 个大写字母(A, B, …, Z)表示。
给定 mm 个不等式,每个不等式形如 X<Y,表示 XX 小于 YY
不等式具有传递性:若 A<BA < BB<CB < C,则 A<CA < C

你需要按顺序处理每个不等式,每读入一个不等式就判断当前所有不等式是否能推导出以下三种情况之一:

  1. 能确定所有变量之间的全序关系(即可确定每个变量的大小顺序) → 输出确定次序的语句,并结束当前数据。
  2. 出现矛盾(例如同时有 A<BA < BB<AB < A,或者由传递性推出 A<AA < A) → 输出矛盾语句,并结束。
  3. 处理完所有 mm 个不等式后仍不能确定全序关系,也无矛盾 → 输出无法确定。

注意:必须从前往后逐个不等式判断,一旦出现情况 1 或 2,立即结束,不再处理剩余不等式。


输入格式

输入包含多组测试数据。
每组数据第一行两个整数 nnmm2n262 \le n \le 26)。
接下来 mm 行,每行一个不等式,格式为 X<Y
当输入 0 0 时,输入终止。

输出格式

每组数据输出一行,结果可能是以下三种之一(具体格式见样例):

  1. Sorted sequence determined after t relations: yyy...y.
    t 是发现能确定全序关系时的迭代次数,即第几个不等式之后;yyy...y 是变量按从小到大排列的序列)
  2. Inconsistency found after t relations.
    t 是发现矛盾时的迭代次数)
  3. Sorted sequence cannot be determined.

数据范围

  • 2n262 \le n \le 26
  • 变量为大写字母 A∼Z

输入样例 1

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

输出样例 1

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

样例解释

第一组数据(n=4, m=6)

不等式序列:

  1. A<B → 当前信息:A<B
  2. A<C → 当前信息:A<B, A<C
  3. B<C → 当前信息:A<B, A<C, B<C → 可推出 A<B<C
  4. C<D → 当前信息:A<B<C<D
    此时所有 4 个变量的大小顺序完全确定:A < B < C < D。
    因此输出:Sorted sequence determined after 4 relations: ABCD.

注意:之后还有两个不等式没有处理,但程序在读完第 4 个不等式后就已经结束本组数据。


第二组数据(n=3, m=2)

不等式序列:

  1. A<B
  2. B<A → 与 A<B 矛盾。
    因此输出:Inconsistency found after 2 relations.

第三组数据(n=26, m=1)

不等式:A<Z
处理完唯一不等式后,26 个变量中只确定了 A<Z,其他变量之间没有关系,无法确定全序。
输出:Sorted sequence cannot be determined.


输入样例 2

6 6
A<F
B<D
C<E
F<D
D<E
E<F
0 0

输出样例 2

Inconsistency found after 6 relations.

解释

已知:

  • A<F
  • B<D
  • C<E
  • F<D
  • D<E
  • E<F

从 D<E 和 E<F 得 D<F,但从 F<D 得 F<D,矛盾(D<F 且 F<D 不可能同时成立)。
因此读完第 6 个不等式后矛盾暴露。


输入样例 3

5 5
A<B
B<C
C<D
D<E
E<A
0 0

输出样例 3

Sorted sequence determined after 4 relations: ABCDE.

解释

已知:

  1. A<B
  2. B<C → A<B<C
  3. C<D → A<B<C<D
  4. D<E → A<B<C<D<E
    此时 5 个变量顺序已完全确定:A<B<C<D<E,所以第 4 个不等式后即可输出。
    第 5 个不等式 E<A 与前面矛盾,但不会读到,因为在第 4 个不等式后已经结束。

这样题目就完整了,附上了清晰的样例解释。