1.拓扑排序可以用来判断图中是否有环,
2.还可以用来判断图是否是一条链。
复制Markdown 展开
一个不同的值的升序排序数列指的是一个从左到右元素依次增大的序列,例如,一个有序的数列 A,B,C,DA,B,C,D 表示A
输入格式
第一行有两个正整数 n,mn,m,nn 表示需要排序的元素数量,2\leq n\leq 262≤n≤26,第 11 到 nn 个元素将用大写的 A,B,C,D\dotsA,B,C,D… 表示。mm 表示将给出的形如 A 接下来有 mm 行,每行有 33 个字符,分别为一个大写字母,一个 若根据前 xx 个关系即可确定这 nn 个元素的顺序 若根据前 xx 个关系即发现存在矛盾(如 A
若根据这 mm 个关系无法确定这 nn 个元素的顺序,输出 (提示:确定 nn 个元素的顺序后即可结束程序,可以不用考虑确定顺序之后出现矛盾的情况) 输入 #1复制 输出 #1复制 输入 #2复制 输出 #2复制 输入 #3复制 输出 #3复制 2 \leq n \leq 26,1 \leq m \leq 6002≤n≤26,1≤m≤600。
这一道题一看就知道是拓扑排序。 1.首先观察数据范围和输出,数据范围26,是真的小,就说明多搞一搞肯定也T不了。输出要求输出到第几次就行了,或者不行了,就说明我们每建一条边就需要一次拓扑排序。 2.再看这道题的三种情况。第一个是有稳定顺序,第二个是有环,第三个是无环但是也没有稳定拓扑顺序。然后我们对这三个问题进行依次解决。 第一个问题:有稳定拓扑排序说明拓扑排序的层数是n。也就是下面代码的val。一层一层下去如果是n层的话,那么这个图里面肯定包含一个n长度的链,我们只要看最大的层数是不是n就可以了,也就是代码的ans==n。 第二个问题就是成环,拓扑排序判断有没有环其实很简单,如果拓扑排序没能遍历所有的点,就说明存在一个环。也就是下面的sum==s1.size()。s1是用来存储目前元素(点)个数的。 最后一种情况最简单,如果前两种都不是,那肯定就是最后一种了! <
符号,一个大写字母,表示两个元素之间的关系。输出格式
yyy..y
(如 ABC
),输出Sorted sequence determined after xxx relations: yyy...y
.Inconsistency found after x relations.
Sorted sequence cannot be determined.
输入输出样例
4 6
A
Sorted sequence determined after 4 relations: ABCD.
3 2
A
Inconsistency found after 2 relations.
26 1
A
Sorted sequence cannot be determined.
说明/提示