A30287. 小字辈
填空题
困难
知识点
题目描述
小字辈
题目描述
本题给定一个庞大家族的家谱，要请你给出最小一辈的名单。
时间限制： 1000 内存限制： 262144
输入
输入在第一行给出家族人口总数 N（不超过 100 000 的正整数） —— 简单起见，我们把家族成员从 1 到 N 编号。随后第二行给出 N 个编号，其中第 i 个编号对应第 i 位成员的父/母。家谱中辈分最高的老祖宗对应的父/母编号为 -1 。一行中的数字间以空格分隔。
输出
首先输出最小的辈分（老祖宗的辈分为 1 ，以下逐级递增） 。
然后在第二行按递增顺序输出辈分最小的成员的编号。
编号间以一个空格分隔，行首尾不得有多余空格。
样例输入
9
2 6 5 5 -1 5 6 4 7
样例输出
4
1 9
参考答案
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int N = 100010;
vector<int>v[N];
int n ,a[N] ,depth[N] ,flag;
int bfs() {
queue<int>q;
q.push(v[0][0]);//根节点只有一个孩子，直接把这个孩子传入队列
int x;
while (!q.empty()) {
x = q.front();
q.pop();
for (int i = 0; i < v[x].size(); i++) {//搜索所有的孩子
depth[v[x][i]] = depth[x] + 1;//深度为父节点+1
q.push(v[x][i]);
}
}
return depth[x];//返回树的深度
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (a[i] == -1) {//将根节点改为0
a[i] = 0;
depth[i] = 1;//根节点的深度为1
}
v[a[i]].push_back(i);//i是a[i]的孩子
}
int ans = bfs();
cout << ans << endl;
for (int i = 1; i <= n; i++) {//遍历找出距离根节点最远的叶节点
if (depth[i] == ans) {
if(flag) cout << ' ';
cout << i ,flag = 1;
}
}
cout << endl;
return 0;
}
上一题
下一题