#P1347. 排序

    ID: 154 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>图论福建省历届夏令营排序拓扑排序

排序

题目描述

一个不同的值的升序排序数列指的是一个从左到右元素依次增大的序列,例如,一个有序的数列 A,B,C,DA,B,C,D 表示A<B,B<C,C<DA<B,B<C,C<D。在这道题中,我们将给你一系列形如 A<BA<B 的关系,并要求你判断是否能够根据这些关系确定这个数列的顺序。

输入格式

第一行有两个正整数 n,mn,mnn 表示需要排序的元素数量,2n262\leq n\leq 26,第 11nn 个元素将用大写的 A,B,C,DA,B,C,D\dots 表示。mm 表示将给出的形如 A<BA<B 的关系的数量。

接下来有 mm 行,每行有 33 个字符,分别为一个大写字母,一个 < 符号,一个大写字母,表示两个元素之间的关系。

输出格式

若根据前 xx 个关系即可确定这 nn 个元素的顺序 yyy..y(如 ABC),输出

Sorted sequence determined after xxx relations: yyy...y.

若根据前 xx 个关系即发现存在矛盾(如 A<B,B<C,C<AA<B,B<C,C<A),输出

Inconsistency found after x relations.

若根据这 mm 个关系无法确定这 nn 个元素的顺序,输出

Sorted sequence cannot be determined.

(提示:确定 nn 个元素的顺序后即可结束程序,可以不用考虑确定顺序之后出现矛盾的情况)

4 6
A<B
A<C
B<C
C<D
B<D
A<B

Sorted sequence determined after 4 relations: ABCD.
3 2
A<B
B<A
Inconsistency found after 2 relations.
26 1
A<Z
Sorted sequence cannot be determined.

提示

2n26,1m6002 \leq n \leq 26,1 \leq m \leq 600