Module: 深入搜索。数字文件系统


Problem

7 /12


拓扑排序

Theory Click to read/hide

算法可以描述如下:
给定一个有 n 个顶点和 m 条边的有向图。需要对其顶点重新编号,使每条边从编号较小的顶点指向编号较大的顶点。
换句话说,就是要找到一个顶点的排列(拓扑序)对应于图中所有边给定的顺序。
我们将使用深度优先搜索 (dfs(v))
如果我们在退出时将顶点添加到列表的开头 \(dfs(v)\) ,那么最后在此列表中,您将获得拓扑排序。
因此,所需的拓扑排序 —这是按退出时间降序排列的。

Problem

给定一个有向未加权图。 需要对其进行拓扑排序。

输入: 第一行包含两个自然数n和m (1≤n≤105, 1≤m≤10< sup >5) ——分别是图中的顶点数和边数。接下来的 m 行列出了图的边。每条边由一对数字给出——分别是开始和结束顶点的数量。
 
输出: 将图的任何拓扑类型打印为顶点数序列。如果无法对图进行拓扑排序,则打印 −1。
第一行包含顶点数 N 和边数 M。 

例子 <头> <日># <正文>
输入 输出
1 4 4
14
4 3
4 2
3 2
1 4 3 2