L2-026 小字辈 (25 分)

简介: L2-026 小字辈 (25 分)

L2-026 小字辈 (25 分)


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


输入格式:


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


输出格式:


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


输入样例:


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


输出样例:


1. 4
2. 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;
}
目录
相关文章
|
7月前
|
存储 编解码
1068 万绿丛中一点红 (20 分)
1068 万绿丛中一点红 (20 分)
|
7月前
1071 小赌怡情 (15 分)
1071 小赌怡情 (15 分)
|
7月前
1002 A+B for Polynomials (25 分)
1002 A+B for Polynomials (25 分)
|
7月前
1062 最简分数 (20 分)
1062 最简分数 (20 分)
L1-070 吃火锅 (15 分)
L1-070 吃火锅 (15 分)
158 0
L1-070 吃火锅 (15 分)
L1-054 福到了 (15 分)
L1-054 福到了 (15 分)
87 0
L1-054 福到了 (15 分)
牛几 (10 分)
牛几 (10 分)
143 0
h0148. 66 (30 分)
h0148. 66 (30 分)
107 0
L3-011 直捣黄龙 (30 分)
L3-011 直捣黄龙 (30 分)
139 0
L1-010 比较大小 (10 分)
L1-010 比较大小 (10 分)
89 0

热门文章

最新文章