F_JustWei's Studio.

L2-026 小字辈

PTA
字数统计: 639阅读时长: 2 min
2021/04/21 Share

L2-026 小字辈

本题给定一个庞大家族的家谱，要请你给出最小一辈的名单。

输入格式：

输入在第一行给出家族人口总数 N（不超过 100 000 的正整数） —— 简单起见，我们把家族成员从 1 到 N 编号。随后第二行给出 N 个编号，其中第 i 个编号对应第 i 位成员的父/母。家谱中辈分最高的老祖宗对应的父/母编号为 -1。一行中的数字间以空格分隔。

输出格式：

首先输出最小的辈分（老祖宗的辈分为 1，以下逐级递增）。然后在第二行按递增顺序输出辈分最小的成员的编号。编号间以一个空格分隔，行首尾不得有多余空格。

输入样例：

1
2
9
2 6 5 5 -1 5 6 4 7

输出样例：

1
2
4
1 9

思路：

  • 建立邻接表
家庭成员 子节点
1
2 1
3
4 8
5 3，4，6
6 2，7
7 9
8
9

  • 找出家谱中辈分最高的老祖宗，并记录其下标

    ​ 下标为5

  • 深搜（dfs），找到没有子节点并且辈分最小的节点

c++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int dir[4][2] = { {1,0} ,{-1,0},{0,1},{0,-1} };
vector<vector<int>>man;
vector<int>ans;
int flag, result;
void dfs(int j, int cnt) {
    //result记录最小辈分，cnt记录当前辈分，man[j].size()==0代表已为叶子节点
	if (result < cnt && man[j].size() == 0) {
		result = cnt;
		ans.clear();
	}

	if (result == cnt)
		ans.push_back(j);

	for (int i = 0; i < man[j].size(); i++) {
		dfs(man[j][i], cnt + 1);
	}
}
int main() {
	int num;

	cin >> num;
	man.resize(num + 1);

    //下标从1开始
	for (int i = 1; i <= num; i++) {
		int t;
		cin >> t;
        //家谱中辈分最高的老祖宗对应的父/母编号为 -1，记录其下标
		if (t == -1) {
			flag = i;
			continue;
		}
		man[t].push_back(i);
	}

    //老祖宗的下标为flag，老祖宗的辈分为 1
	dfs(flag, 1);

    //输出最小的辈分
	cout << result << endl;
	
    //递增顺序
	sort(ans.begin(), ans.end());

    //编号间以一个空格分隔，行首尾不得有多余空格
	for (int i = 0; i < ans.size(); i++) {
		if (i != 0)
			cout << " ";
		cout << ans[i];
	}

    return 0;
}
/*

*/

原文作者：F_JustWei

原文链接：http://139.196.79.90/2021/04/21/L2-026-%E5%B0%8F%E5%AD%97%E8%BE%88/

发表日期：April 21st 2021, 5:05:55 pm

更新日期：April 28th 2021, 2:39:06 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. L2-026 小字辈
    1. 1.0.1. 输入格式：
    2. 1.0.2. 输出格式：
    3. 1.0.3. 输入样例：
    4. 1.0.4. 输出样例：
    5. 1.0.5. 思路：
    6. 1.0.6. c++代码
Total : 130
2021
2019
leetcode 动态规划 字符串 树 数据结构 C++ STL algorithm 容器 操作系统 软考 Java PTA 计算机网络 UML 迭代器 C JSON 信息安全 模板 多媒体， 软考 数据库 软件工程 排序 Spring 人机交互