Topological Sort Using BFS (Kahn's Algorithm)
Produce a topological ordering of a directed acyclic graph using Kahn's BFS-based algorithm.
Input format
The first line contains N and M. The next M lines contain directed edge pairs (DAG).
Output format
Print Kahn's algorithm order: initial zero-indegree vertices in ascending order, neighbors relaxed in ascending order.
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
5 4
2 4
2 3
3 4
0 2Expected output
0 1 2 3 4Example 2
Input
23 25
21 22
5 7
11 21
17 21
13 14
18 21
15 16
5 10
8 19
4 16
9 20
18 20
18 22
10 16
12 17
0 19
3 12
13 15
17 18
9 16
0 2
16 19
2 16
0 1
14 20Expected output
0 3 4 5 6 8 9 11 13 1 2 12 7 10 14 15 17 16 18 19 20 21 22