题解 | 【模板】拓扑排序

import sys
from collections import deque

def topological_sort(n, m ,edges):
    adj = [[] for _ in range(n+1)] # 接邻表
    in_degree = [0]*(n+1) # 入度数组
    for u, v in edges:
        adj[u].append(v)
        in_degree[v] += 1
    
    # 入度为0的队列
    q = deque()
    for i in range(1,n+1):
        if in_degree[i] == 0:
            q.append(i)

    # 拓扑排序数组
    result = []
    while q:
        u = q.popleft()
        result.append(u)
        for v in adj[u]:
            in_degree[v] -=1
            if in_degree[v] == 0:
                q.append(v)
    if len(result) != n:
        return -1
    return result

n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]
result = topological_sort(n, m, edges)

# 输出结果
if result == -1:
    print(-1)
else:
    print(" ".join(map(str, result)))