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;
}
目录
相关文章
|
6月前
深度优先搜索(DFS、深搜)和广度优先搜索(BFS、广搜)(下)
深度优先搜索(DFS、深搜)和广度优先搜索(BFS、广搜)
35 0
|
6月前
|
算法
深度优先搜索(DFS、深搜)和广度优先搜索(BFS、广搜)(上)
深度优先搜索(DFS、深搜)和广度优先搜索(BFS、广搜)
82 0
|
6月前
|
存储 人工智能
深度优先搜索(DFS、深搜)和广度优先搜索(BFS、广搜)(中)
深度优先搜索(DFS、深搜)和广度优先搜索(BFS、广搜)
42 0
|
机器学习/深度学习 算法 测试技术
C++算法:01BFS最短距离的原理和实现
C++算法:01BFS最短距离的原理和实现
|
存储 机器人 C++
|
机器学习/深度学习 Java
【每日一题Day64】LC1799N 次操作后的最大分数和 | 状态压缩dp 状态压缩+dfs+记忆化搜索
每个数字有两种状态,删除或者未删除,因此可以使用状态压缩记录未删除的数字情况state,便于使用位运算进行状态的遍历及转移;使用状态压缩dp找到将所以数字删除的最大分数
102 0
【每日一题Day64】LC1799N 次操作后的最大分数和 | 状态压缩dp 状态压缩+dfs+记忆化搜索
|
算法
BFS——二分图判断
BFS——二分图判断
118 0
BFS——二分图判断
|
存储
L2-031 深入虎穴 (25 分)(bfs)
L2-031 深入虎穴 (25 分)(bfs)
203 0
L2-031 深入虎穴 (25 分)(bfs)
L3-008 喊山 (30 分)(bfs)
L3-008 喊山 (30 分)(bfs)
101 0
L3-008 喊山 (30 分)(bfs)
|
存储 算法 C语言
6-1 最小生成树(普里姆算法) (10分)
6-1 最小生成树(普里姆算法) (10分)
6-1 最小生成树(普里姆算法) (10分)