L2-026 小字辈 (25 分)(bfs)

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

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


输入格式:

输入在第一行给出家族人口总数 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


思路:建立家谱图,用bfs依次往下遍历,用level存每个人离祖宗节点的距离,最小的辈分就是离祖先最远距离的节点

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<int>v[N];//存关系
int level[N];//存层次
int n;
void bfs(int u)
{
    queue<int>q;
    q.push(u);
    while(q.size())
    {
        int x=q.front();
        q.pop();
        for(int i=0;i<v[x].size();i++)
        {
            if(!level[v[x][i]])
            {
                q.push(v[x][i]);
                level[v[x][i]]=level[x]+1;
            }
        }
    }
    int maxl=-1;
    for(int i=1;i<=n;i++)
        if(maxl<level[i]) maxl=level[i];
    int f=0;
    cout<<maxl+1<<endl;//加上根节点
    for(int i=1;i<=n;i++)
        if(level[i]==maxl)//叶子节点
        {
            if(f++) cout<<' ';
            cout<<i;
        }
}
int main()
{
    cin>>n;
    int t,x;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        if(x==-1) t=i;//祖宗节点
        else v[x].push_back(i);
    }
    bfs(t);
    return 0;
}
目录
相关文章
|
机器学习/深度学习 存储 算法
【DFS经典例题】2n皇后问题
【DFS经典例题】2n皇后问题
76 0
|
机器学习/深度学习 算法 测试技术
C++算法:01BFS最短距离的原理和实现
C++算法:01BFS最短距离的原理和实现
|
存储 索引
树与图中的dfs和bfs—— AcWing 846. 树的重心 AcWing 847. 图中点的层次
树与图中的dfs和bfs—— AcWing 846. 树的重心 AcWing 847. 图中点的层次
78 0
|
算法
BFS——二分图判断
BFS——二分图判断
120 0
BFS——二分图判断
|
存储
L2-031 深入虎穴 (25 分)(bfs)
L2-031 深入虎穴 (25 分)(bfs)
203 0
L2-031 深入虎穴 (25 分)(bfs)
L3-008 喊山 (30 分)(bfs)
L3-008 喊山 (30 分)(bfs)
102 0
L3-008 喊山 (30 分)(bfs)
|
存储 算法 C语言
6-1 最小生成树(普里姆算法) (10分)
6-1 最小生成树(普里姆算法) (10分)
6-1 最小生成树(普里姆算法) (10分)
|
算法 Java Python
【算法题解】 Day6 BFS | DFS
今天的算法是 「BFS | DFS」 相关,“算法题解系列文章旨在精选重点与易错的算法题,总结常见的算法思路与可能出现的错误,以实战习题的形式理解算法,使用算法。”
103 0
【CCCC】L3-008 喊山 (30分),BFS搜索最长路,水题
【CCCC】L3-008 喊山 (30分),BFS搜索最长路,水题
107 0
|
算法 C++ Python
BFS逛街算法模板-附LeetCode习题-433. 最小基因变化-广度优先搜索
BFS逛街算法模板-附LeetCode习题-433. 最小基因变化-广度优先搜索