← 返回 netflix 的题目列表Topological Sort
类型：online_judge
Problem: Topological Sort
Given a directed graph with n nodes labeled 0..n-1 and a list of directed edges edges. Each edge is a pair (u, v) meaning u -> v.
Return any topological ordering: a sequence of all n nodes such that for every edge u -> v, u appears before v in the sequence.
If the graph contains a cycle (so no topological ordering exists), output an empty sequence.
Input Format
Line 1: integer n (number of nodes)
Line 2: integer m (number of edges)
Next m lines: two integers u v representing an edge u -> v
Output Format
Print one line:
If a topological ordering exists, print n integers separated by spaces.
Otherwise print an empty line.
Constraints
1 <= n <= 2 * 10^5
0 <= m <= 2 * 10^5
0 <= u, v < n
Sample Tests
input:
4
4
0 1
0 2
1 3
2 3
output:
0 1 2 3
input:
2
2
0 1
1 0
output:
input:
3
0
output:
0 1 2
input:
5
4
0 2
1 2
2 3
2 4
output:
0 1 2 3 4
input:
1
0
output:
0
Example
Input
4
4
0 1
0 2
1 3
2 3
Output
0 1 2 3