题解 | 【模板】拓扑排序

import sys
from collections import deque

a = sys.stdin.read().split()
# number of nodes and number of edges
n,m = int(a[0]),int(a[1]) 

edge = []
adj = [[] for _ in range(n+1)]
in_degree = [0]*(n+1)
idx = 2
for _ in range(m):
    u,v = int(a[idx]),int(a[idx+1]) 
    edge.append((u,v))
    # build the adjcent list and record the in_degree
    adj[u].append(v)
    in_degree[v] += 1
    idx += 2
# print(in_degree)

queue = deque()
for v in range(1,n+1):
    if in_degree[v] == 0:
        queue.append(v)

topo_order =[]
while queue:
    u = queue.popleft()
    topo_order.append(u)
    for v in adj[u]:
        in_degree[v] -= 1
        if in_degree[v] == 0:
            queue.append(v)


if len(topo_order) == n:
    print(' '.join(map(str,topo_order)))
else:
    print(-1)