1191 家谱树(拓扑排序)

1191 家谱树(拓扑排序)1 问题描述 有个人的家族很大 辈分关系很混乱 请你帮整理一下这种关系 给出每个人的孩子的信息 输出一个序列 使得每个人的孩子都比那个人后列出 输入格式第 1 行一个整数 n 表示家族的人数 接下来 n 行 第 i 行描述第 i 个人的孩子 每行最后是 0 表示描述完毕 每个人的编号从 1 到 n 输出格式输出一个序列 使得每个人的孩子都比那个人后列出 数据保证一定有解 如果有多解输出任意一解 数据范围 1 n 100 输入样例

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

(0)
全栈程序员-站长的头像全栈程序员-站长


相关推荐

  • j-link接口定义及实际使用[通俗易懂]

    j-link接口定义及实际使用[通俗易懂]使用j-link下载程序或者在线调试的时候,有两种模式:JTAG和SWD可以在keil中选择:下面是两种模式下,分别用的接口引脚:推荐使用SWD模式,因为更省引脚而且调试功能不受影响。在SWD模式下,实际只需要4个IO口就可以了,包括下载程序和在线调试。分别为:PA13/JTMS/SWDIO、PA14/JTCK/SWCLK、VCC、GND

    2022年5月28日
    108
  • verilog流水线设计代码_流水线cpu设计verilog

    verilog流水线设计代码_流水线cpu设计verilog介绍定义:流水线设计就是将组合逻辑分割,并在各级之间插入寄存器,暂存中间数据的方法。以面积换速度。优点:每一部分延时降低——可用更快的时钟;大部分电路同时运算——提高数据吞吐率。缺点:增加面积;流水线并不减小单个数据操作的时间,减小的是整个数据流的操作时间;(不懂)功耗增加,硬件复杂度增加,特别对于复杂逻辑如cpu的流水线而言,流水越深,发生需要hold流水线或reset流水线的情况时,时间损失越大。所以使用流水线并非有利无害,大家需权衡考虑。应用场景:1)组合逻辑太长,

    2022年8月14日
    4
  • windows程序设计第五版_windows程序设计入门

    windows程序设计第五版_windows程序设计入门Ellipse函数的用法函数功能:该函数用于画一个椭圆,椭圆的中心是限定矩形的中心,使用当前画笔画椭圆,用当前的画刷填充椭圆。函数原型:BOOL Ellipse(HDC hdc, int nLeftRect, int nTopRect, nRightRect, int nBottomRect);参数:hdc:设备环境句柄。nLeftRect:指定限定矩形左上角的X坐标。nTopRect…

    2022年8月18日
    7
  • cas与乐观锁(jpa乐观锁)

    独占锁是一种悲观锁,synchronized就是一种独占锁;它假设最坏的情况,并且只有在确保其它线程不会造成干扰的情况下执行,会导致其它所有需要锁的线程挂起直到持有锁的线程释放锁。所谓乐观锁就是每次不加锁,假设没有冲突而去完成某项操作;如果发生冲突了那就去重试,直到成功为止。CAS(CompareAndSwap)是一种有名的无锁算法。CAS算法是乐观锁的一种实现。CAS有3个操作数,内…

    2022年4月15日
    219
  • BZOJ 1798 [Ahoi2009]Seq 维护序列seq 线段树

    BZOJ 1798 [Ahoi2009]Seq 维护序列seq 线段树

    2022年2月5日
    30
  • Jmeter参数化请求

    Jmeter参数化请求参数化请求

    2025年9月19日
    4

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号