图论——拓扑排序（python）

思路统计节点的入度将入度为0的节点放入队列中循环出队。对于出队元素找到它指向的所有元素将所指向的元素的入度减一。#拓扑排序 from collections import deque def topologicalOrder(graph,indegree,n): qdeque() res[] for i in range(n): if indegree[i]0: q.append(i) #入度为0的节点加入队列 while q: xq.popleft() res.append(x) nodegraph[x] #拿到x指向的元素集合 for i in node: indegree[i]-1 if indegree[i]0: q.append(i) if len(res)!n: return -1 return 1 def main(): n,mmap(int,input().split()) #n个节点m条边 graph[[] for _ in range(n)] #存图 indegree[0]*(n) #统计节点入度 for i in range(m): a,bmap(int,input().split()) graph[a].append(b) indegree[b]1 restopologicalOrder(graph,indegree,n) print(res) return if __name____main__: main()