OpenJudge

E08P01:DAG上的拓扑排序

总时间限制:
1000ms
内存限制:
65536kB
描述

给定有向无环图G(V,E),求G的一个拓扑排序。请使用DFS+stack的算法。

输入
第一行包含两个整数N、M,表示该图共有N个结点和M条有向边。(N <= 5000,M <= 200000)
接下来M行,每行包含2个整数{u,v},表示有一条有向边 u指向v
输出
一行,代表图G的拓扑排序序列,空格隔开。
样例输入
5 6
1 2
1 5
2 3
3 5
3 4
4 5
样例输出
1 2 3 4 5
提示
* for(int i=1;i<=N;i++)
{
if(prev[i]==-1) dfs(i);
}
全局题号
15332
添加于
2017-07-28
提交次数
15
尝试人数
10
通过人数
9