AcWing 1191. 家谱树
原题链接
简单
作者:
皓首不倦
,
2020-08-24 22:14:51
,
所有人可见
,
阅读 510
'''
简单进行拓扑排序即可
'''
import sys
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 = int(input())
edges = []
for i in range(1, n+1):
s = sys.stdin.readline()
arr = map(int, s.split())
for val in arr:
edges.append((val, i))
ans = TopoSort.sort(edges)
for val in ans[:-1]:
print(val, end=' ')