1. 拓扑排序(卡码网 117)
from collections import deque, defaultdict
def main():
num_node, num_edge = map(int, input().split())
inDegrees = [0 for _ in range(num_node)]
edges = defaultdict(list)
for _ in range(num_edge):
source, target = map(int, input().split())
inDegrees[target] += 1
edges[source].append(target)
# 将入度为0的顶点入度
que = deque([i for i in range(num_node) if inDegrees[i] == 0])
result = []
while que:
cur = que.popleft()
result.append(cur)
for t in edges[cur]:
inDegrees[t] -= 1
if inDegrees[t] == 0:
que.append(t)
if len(result) == num_node:
print(" ".join(map(str, result)))
else:
print(-1)
if __name__ == "__main__":
main()
标签:__,node,图论,拓扑,num,que,result,inDegrees,排序
From: https://www.cnblogs.com/hifrank/p/18523107