题解 | 【模板】拓扑排序

from collections import defaultdict
class Graph:
    def __init__(self) -> None:
        self.gragh = defaultdict(list)
    
    def add_egde(self, start, end):
        self.gragh[start].append(end)
        self.gragh[end] = self.gragh[end]

    def topo_sort(self) -> list:
        in_degree = {node:0 for node in self.gragh}
        for node in self.gragh:
            for adj in self.gragh[node]:
                in_degree[adj] += 1

        q = []
        for node, v in in_degree.items():
            if v == 0:
                q.append(node)
        for u in q:
            for v in self.gragh[u]:
                in_degree[v] -= 1
                if in_degree[v] == 0:
                    q.append(v)
        
        if len(q) < len(self.gragh):
            return []
        return q

n, m = map(int, input().split())
topo_gragh = Graph()
for _ in range(m):
    u, v = map(int, input().split())
    topo_gragh.add_egde(u, v)

res = topo_gragh.topo_sort()
if res:
    print(' '.join(map(str, res)))
else:
    print(-1)