Topological Sort Using DFS
Produce a topological ordering of a directed acyclic graph using DFS.
Input format
The first line contains N and M. The next M lines contain directed edge pairs (DAG — generate u < v).
Output format
Print DFS-based topological order: iterate vertices 0..n-1, visit neighbors in ascending order, push on finish, reverse.
Constraints
- Values fit in a 64-bit signed integer
- Trailing whitespace and a trailing newline are ignored by the judge
Read from stdin, write to stdout. Sample cases below show the exact format.
Sample cases
Example 1
Input
16 29
3 13
3 12
6 11
9 14
5 14
6 10
5 11
0 9
1 12
10 15
1 6
8 12
12 14
10 11
9 10
14 15
4 13
6 14
11 13
13 14
1 8
13 15
11 14
5 15
11 15
11 12
8 15
0 15
0 7Expected output
5 4 3 2 1 8 6 0 9 10 11 13 12 14 15 7Example 2
Input
10 26
7 9
5 6
6 7
0 9
8 9
2 5
5 9
3 9
0 2
1 7
1 2
1 8
3 8
4 6
7 8
0 8
2 9
4 5
1 3
2 3
2 4
3 4
2 8
4 7
5 8
5 7Expected output
1 0 2 3 4 5 6 7 8 9