题解 | 【模板】拓扑排序

构造拓扑序列步骤

1. 从图中选择一个入度为零的点。
2. 输出该顶点，从图中删除此顶点及其所有的出边。

重复上面两步，直到所有顶点都输出，拓扑排序完成，或者图中不存在入度为零的点，此时说明图是有环图，拓扑排序无法完成，陷入死锁。

import sys

E_num: int = None
V_num: int = None

graph: list = None
graph_T: list = None

for i, line in enumerate(sys.stdin):
    a = line.split()
    
    if not a: continue

    if i == 0:
        E_num, V_num = int(a[0]), int(a[1])
        graph = [[] for _ in range(E_num)]
        graph_T = [[] for _ in range(E_num)]
        continue

    graph[int(a[0])-1].append(int(a[1])-1)
    graph_T[int(a[1])-1].append(int(a[0])-1)
    
in_dim = [len(l) for l in graph_T] # 获得所有顶点的入度
index = list(range(E_num))
mask = [False for _ in in_dim]

in_dim_0_node = [i for i in index if in_dim[i] == 0] # 存储入度为0的节点

out_graph = []

while in_dim_0_node:
    i = in_dim_0_node.pop() # 获得一个入度为0的节点
    for e_i in graph[i]:
        in_dim[e_i] -= 1
        if in_dim[e_i] == 0:
            in_dim_0_node.append(e_i)
    out_graph.append(i+1)


if(len(out_graph)==len(in_dim)):
    print(*out_graph)
else:
    print(-1)