1191 家谱树（拓扑排序）

全栈程序员-站长 • 2025年9月7日下午3:15 • 未分类 • 阅读 0

1. 问题描述：

有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。给出每个人的孩子的信息。输出一个序列，使得每个人的孩子都比那个人后列出。

输入格式

第 1 行一个整数 n，表示家族的人数；接下来 n 行，第 i 行描述第 i 个人的孩子；每行最后是 0 表示描述完毕。每个人的编号从 1 到 n。

输出格式

输出一个序列，使得每个人的孩子都比那个人后列出；数据保证一定有解，如果有多解输出任意一解。

数据范围

1 ≤ n ≤ 100

输入样例：

输出样例：

2. 思路分析：

分析题目可以知道我们可以将每一个人看成是一个节点，本质上求解的是拓扑排序的序列，拓扑排序是对于有向图来说的，使得每一条边都是前面的节点指向后面的节点，当存在环的时候是没有拓扑排序的，如果一个有向图可以拓扑排序那么这个图称为拓扑图，拓扑图等价于有向无环图。算法流程：

遍历每一条边的时候统计节点的入度；
将所有入度为0的点入队，当队列非空的时候执行循环，弹出队头元素，遍历队头元素的所有出边，将出边对应的节点的入度减1，如果发现度数为0之后那么将其加入到队列中，并且所有度数为0的节点都是拓扑排序的序列。

3. 代码如下：

import collections from typing import List class Solution: def topsort(self, n: int, d: List[int], g: List[List[int]], res: List[int]): q = collections.deque() for i in range(1, n + 1): # 将入度为0的点入队 if d[i] == 0: q.append(i) res.append(i) while q: # 弹出队首节点 p = q.popleft() # 遍历p的所有邻接点 for next in g[p]: # 对应的入度减1 d[next] -= 1 # 入度为0之后将当前节点加入到队列中 if d[next] == 0: q.append(next) # 拓扑排序的序列中加入当前的节点next res.append(next) def process(self): n = int(input()) # 邻接表 g = [list() for i in range(n + 10)] d = [0] * (n + 10) for i in range(1, n + 1): s = input() # 当len(s) == 1的时候说明没有孩子 if len(s) > 1: s = s.split() for j in range(len(s) - 1): t = int(s[j]) g[i].append(t) d[t] += 1 res = list() # 拓扑排序 self.topsort(n, d, g, res) for x in res: print(x, end=" ") if __name__ == "__main__": Solution().process()

from typing import List import collections class Solution: def process(self): n = int(input()) g = [list() for i in range(n + 10)] # d用来统计入度 d = [0] * (n + 10) for i in range(1, n + 1): s = input().split() if len(s) > 1: for j in range(len(s) - 1): t = int(s[j]) g[i].append(t) d[t] += 1 res = list() self.topsort(n, d, g, res) for x in res: print(x, end=" ") def topsort(self, n: int, d: List[int], g: List[List[int]], res: List[int]): q = collections.deque() for i in range(1, n + 1): if d[i] == 0: q.append(i) while q: p = q.popleft() # 每一个弹出来的节点都是入度为0的点为拓扑排序的序列 res.append(p) for next in g[p]: d[next] -= 1 if d[next] == 0: q.append(next) if __name__ == "__main__": Solution().process()

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/232829.html原文链接：https://javaforall.net