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

Problem

7 /12

算法可以描述如下：
给定一个有 n 个顶点和 m 条边的有向图。需要对其顶点重新编号，使每条边从编号较小的顶点指向编号较大的顶点。

换句话说，就是要找到一个顶点的排列（拓扑序）对应于图中所有边给定的顺序。
我们将使用深度优先搜索 (dfs(v))

如果我们在退出时将顶点添加到列表的开头 \(dfs(v)\) ，那么最后在此列表中，您将获得拓扑排序。

因此，所需的拓扑排序 —这是按退出时间降序排列的。

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

输入： 第一行包含两个自然数n和m (1≤n≤10⁵, 1≤m≤10< sup >5) ——分别是图中的顶点数和边数。接下来的 m 行列出了图的边。每条边由一对数字给出——分别是开始和结束顶点的数量。

输出： 将图的任何拓扑类型打印为顶点数序列。如果无法对图进行拓扑排序，则打印 −1。

第一行包含顶点数 N 和边数 M。

例子 <头> <日># <正文>

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

输入	输出
1	4 4 14 4 3 4 2 3 2	1 4 3 2