题解 | #【模板】拓扑排序#

from collections import deque

n,m = map(int,input().split())

root = [0]*n    #顶点矩阵，存储能够到达0~n-1的点
d = [[] for _ in range(n)]   #存储0~1能够能够到达哪些点
route = deque([])
for i in range(m):
    u,v = map(int,input().split())
    root[v-1]+=1
    d[u-1].append(v-1)

dp = []
route = deque([i for i in range(n) if not root[i]])

while len(route):
    j = route.popleft()
    dp.append(j+1)
    for i in d[j]:
        root[i] = root[i]-1
        if root[i]==0:
            route.append(i)

if len(dp)==n:
    print(*dp)

else:
    print(-1)

我发现我每次写程序时间都超长了，必须要手动去改一下队列之类的

拓扑排序思路：

1、统计每个节点的入度数和邻接的节点。意思比如节点1，有2个点可以通过有向线跟它相连，入度数就是2；如果节点1可以到达点2，点3，那么邻接的点就是2、3；（注意：入度不需要统计具体的点，只需要统计数量就行）

2、将入度数为0的点放入队列

3、①选择队列里面的第一个节点②将这个节点存下来③将该节点的邻接点的入度数减1④将入度数为0的节点放进队列

4、循环3

5、统计存下的节点，如果节点数为n，那么存在拓扑序列，输出即可；反之，不存在，输出-1