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
