对于给定的由 个顶点、 条边构成的有向图(不一定连通)。检查图中是否存在任意的简单环。若不存在,输出该图字典序最小的拓扑序列。 【名词解释】 简单环:至少包含 个顶点,且没有重复顶点或边的环。更具体地,设在有向图上存在 个不同的顶点构成的序列 ,使得对于任意的 ,均存在有向边 ,且存在有向边 ,则称这个序列构成一个简单环。这个序列与其循环同构的序列被视为同一个简单环。 数组的字典序比较:从左到右逐个比较两个数组的元素。如果在某个位置上元素不同,比较这两个元素的大小,元素小的数组字典序也小。如果一直比较到其中一个数组结束,则长度较短的数组字典序更小。 在本题中,由于给定多重图,我们将简单环(顶点不重复的闭合有向路)的定义拓展为「至少包含 个顶点」,在学界这是常见的做法。但请注意,在默认定义中,简单环应当至少包含 个顶点。
输入描述:
第一行输入两个整数 ,表示顶点数量、边数量。此后 行,第 行输入两个整数 和 ,表示图上第 条边从顶点 连向顶点 。图可能不连通、可能存在重边。不存在自环。
输出描述:
如果存在简单环,输出 。否则,在第一行上输出 个整数,表示该图的字典序最小的拓扑序列。
示例1
输入
6 7
1 2
3 1
2 4
5 1
4 1
3 1
6 3
说明
该样例如下图所示。

示例2
输入
7 7
1 2
3 2
4 2
1 5
4 5
3 5
6 7
说明
该样例如下图所示。

加载中...