请输出以下问题的代码本题给定一个庞大家族的家谱,要请你给出最小一辈的名单。 输入格式: 输入在第一行给出家族人口总数 N(不超过 100 000 的正整数) —— 简单起见,我们把家族成员从 1 到 N 编号。随后第二行给出 N 个编号,其中第 i 个编号对应第 i 位成员的父/母。家谱中辈分最高的老祖宗对应的父/母编号为 -1。一行中的数字间以空格分隔。 输出格式: 首先输出最小的辈分(老祖宗的辈分为 1,以下逐级递增)。然后在第二行按递增顺序输出辈分最小的成员的编号。编号间以一个空格分隔,行首尾不得有多余空格。 输入样例: 9 2 6 5 5 -1 5 6 4 7 输出样例: 4 1 9
时间: 2024-01-24 15:19:20 浏览: 49
这道题可以使用拓扑排序来解决。
具体的,我们可以先通过输入数据构造出一个以每个人为节点,每个人的子女为边的有向图,然后进行拓扑排序,每次删除入度为 0 的点,并且记录这一批入度为 0 的点的编号,直到删除了所有点为止。
删除的顺序就是我们需要输出的编号,最后输出删除的最后一批编号的最小值即可。
时间复杂度为 O(N),可以通过本题。
相关问题
本题要求将给定的n个整数从大到小排序后输出。 输入格式: 输入第一行给出一个不超
过1000的正整数n,随后一行给出n个整数,数字间以空格分隔。
要求输出n个整数从大到小排序后的结果,数字间以空格分隔,但行末不得有空格。输入输出样例
输入样例:
4
5 -3 32 1
输出样例:
32 5 1 -3
要解决这个问题,我们可以使用python内置的sort方法,将输入的n个整数进行排序。首先读入第一行的正整数n,然后再读入一行n个整数。将这n个整数转换为一个列表,然后对这个列表调用sort方法,按降序排列。最后,将列表转换为字符串,将列表中的每个整数加上空格,然后将其输出。
代码如下:
```python
n = int(input())
nums = list(map(int, input().split()))
nums.sort(reverse=True)
output = ''
for num in nums:
output += str(num) + ' '
print(output[:-1])
```
本题给定一个庞大家族的家谱,要请你给出最小一辈的名单。 输入格式: 输入在第一行给出家族人口总数 N(不超过 100 000 的正整数) —— 简单起见,我们把家族成员从 1 到 N 编号。随后第二行给出 N 个编号,其中第 i 个编号对应第 i 位成员的父/母。家谱中辈分最高的老祖宗对应的父/母编号为 -1。一行中的数字间以空格分隔。 输出格式: 首先输出最小的辈分(老祖宗的辈分为 1,以下逐级递增)。然后在第二行按递增顺序输出辈分最小的成员的编号。编号间以一个空格分隔,行首尾不得有多余空格。 输入样例: 9 2 6 5 5 -1 5 6 4 7 输出样例: 4 1 9 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB
这道题可以用树的深度优先遍历(DFS)进行解决,具体步骤如下:
1.先将家族成员的父母关系存储在一个数组中,如 parent[i] 表示第 i 个成员的父母编号。
2.利用 DFS 找到整个家族的最小辈分 depth,即老祖宗的辈分。具体过程是,从每个成员开始进行 DFS,每进行一次 DFS,depth 就加一,最终取所有 DFS 深度的最大值即为整个家族的最小辈分。
3.再次利用 DFS,找到所有最小辈分的成员编号,具体过程是,从每个成员开始进行 DFS,如果当前深度等于 depth,就将该成员的编号加入结果集。最终将结果集按编号递增排序后输出即可。
下面是 AC 代码:
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)