#D1050. 排序
排序
题目描述
给定 个互不相同的大写字母(即前 个大写字母)和 条形如 的大小关系。这些关系按输入顺序给出。
你需要按顺序加入这些关系,并判断:
- 是否已经能唯一确定这 个字母从小到大排列的顺序;
- 是否出现了矛盾,即同时存在 与 ;
- 如果都没有,继续加入下一条关系。
请求出最早能在第几条关系后确定顺序或发现矛盾,并输出对应的顺序或矛盾信息。
输入格式
第一行两个整数 。
接下来 行,每行一个形如 X<Y 的关系,表示字母 小于字母 。字母只会在前 个大写字母中出现。
输出格式
输出一行,格式为以下三种之一:
- 如果在第 条关系后能唯一确定顺序,输出
Sorted sequence determined after x relations: yyy...y.
其中yyy...y是排好的字母序列; - 如果在第 条关系后发现矛盾,输出
Inconsistency found after x relations.; - 如果所有关系都无法确定顺序,输出
Sorted sequence cannot be determined.。
样例
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.
样例解释
样例 1 中,处理到第 4 条关系 C<D 时,已经能推出 ,顺序唯一;后面的关系不会再改变结果。
样例 2 中,前两条关系同时给出 和 ,出现矛盾,因此在第 2 条关系后输出矛盾。
样例 3 中,只有 一条关系,其余 24 个字母之间没有足够信息,无法确定完整顺序。
数据范围与约定
| 子任务 | 分值 | 限制 |
|---|---|---|
| , | ||
| ,,保证所有关系不产生矛盾 | ||
| , |
- 关系可能重复出现;重复关系不会改变已有信息;
- 字母只会在前 个大写字母中出现;
- 子任务 2 的“保证所有关系不产生矛盾”是指:无论取前多少条关系,都不会同时推出 和 。