Earliest Topological Sort
Given a directed acyclic graph (DAG) with N nodes (numbered 1 to N) and M edges, find a topological sort of the nodes such that the resulting sequence is lexicographically smallest among all possible topological sorts. If multiple edges exist between the same pair of nodes, or if there is a self-loop, ignore them. The graph is guaranteed to be a DAG.
Input
The first line contains two integers N and M, the number of nodes and edges. The next M lines each contain two integers u and v, representing a directed edge from node u to node v.
Output
Print N integers, the nodes in the lexicographically smallest topological sort.
Constraints
1 <= N <= 200000, 0 <= M <= 200000. Nodes are numbered 1 to N.
Example 1
4 4 1 2 1 3 2 4 3 4
1 2 3 4
Nodes 1, 2, and 3 have in-degree 0 initially. Smallest is 1. Then 2 and 3 are available. Smallest is 2. Then 3 is available. Then 4.
Example 2
5 3 1 2 3 4 1 5
1 2 3 4 5
Nodes 1, 3 have in-degree 0. Smallest is 1. Then 2 and 5 are available. Smallest is 2. Then 5. Then 3. Then 4.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
4 4 1 2 1 3 2 4 3 4
5 3 1 2 3 4 1 5