AcWing 848. 有向图的拓扑序列 简单BFS拓扑排序
原题链接
简单
作者:
皓首不倦
,
2020-08-09 16:12:37
,
所有人可见
,
阅读 529
from typing import List
from collections import deque
from collections import Counter
class TopoSort:
# edges是边列表, (a, b)代表一条边,表示a依赖于b, 返回拓扑排序之后的节点列表, 无法完成拓扑排序返回None
@staticmethod
def sort(edges: List):
dep_cnt = Counter() # 每一个节点的依赖计数
link = {}
for a, b in edges:
if a not in link:
link[a] = []
if b not in link:
link[b] = []
link[b].append(a) # link[b]记录哪些点依赖b
if a not in dep_cnt:
dep_cnt[a] = 0
if b not in dep_cnt:
dep_cnt[b] = 0
dep_cnt[a] += 1
ans = []
valid_node = deque() # 当前入度为0的所有节点
for node, degree in dep_cnt.items():
if degree == 0:
valid_node.append(node)
while len(ans) < len(link):
if len(valid_node) == 0:
return None
cur_node = valid_node.popleft()
for next in link[cur_node]:
dep_cnt[next] -= 1
if dep_cnt[next] == 0:
valid_node.append(next)
ans.append(cur_node)
return ans
n, m = map(int, input().split())
edges = []
for i in range(m):
a, b = map(int, input().split())
edges.append((b, a))
topo = TopoSort()
ans = topo.sort(edges)
if ans is None:
print(-1)
else:
print( ' '.join(map(str, ans)) )