问题2098--全排序

2098: 全排序

时间限制: 1 Sec  内存限制: 128 MB
提交: 12  解决: 6
[提交] [状态] [讨论版] [命题人:]

题目描述

不同值的升序排序序列是使用某种形式的小于运算符从小到大排序的元素序列。例如,排序后的序列ABCD表示A<B、B<C和C<D。给定一组A<B形式的关系,要求确定是否指定已排序的订单。

输入

输入包含多个测试用例。每个测试用例的第1行都包含两个正整数n (2≤n ≤26)和m 。n 表示要排序的对象数量,排序的对象是大写字母的前n 个字符。m 表示将给出的A<B形式的关系的数量。接下来的m 行,每行都包含一种由3个字符组成的关系:第1个大写字
母、字符“<”和第2个大写字母。n =m =0的值表示输入结束。

输出

对于每个问题实例,其输出都由一行组成,该行应该是以下三种之一。
• 在x 种关系之后确定的排序顺序:yyy …y 。
• 无法确定排序顺序。
• 在x 种关系后发现不一致。
其中,x 是在确定排序序列或找到不一致时处理的关系数,以先到者为准,yyy …y 是已排序的升序序列。

样例输入 Copy

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

样例输出 Copy

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

来源/分类