一、题目要求
本题给定一个庞大家族的家谱，要请你给出最小一辈的名单。
输入格式：
输入在第一行给出家族人口总数 N（不超过 100 000 的正整数） —— 简单起见，我们把家族成员从 1 到 N 编号。随后第二行给出 N 个编号，其中第 i 个编号对应第 i 位成员的父/母。家谱中辈分最高的老祖宗对应的父/母编号为 -1。一行中的数字间以空格分隔。
输出格式：
首先输出最小的辈分（老祖宗的辈分为 1，以下逐级递增）。然后在第二行按递增顺序输出辈分最小的成员的编号。编号间以一个空格分隔，行首尾不得有多余空格。
输入样例：
9
2 6 5 5 -1 5 6 4 7
输出样例：
4
1 9二、思路
三、代码
1.dfs代码
#include<bits/stdc++.h>
#define endl '\n'
#define x first
#define y second
#define int long long
using namespace std;
typedef pair<int,int>PII;
const int N=2e5+10;
const int inf=0x3f3f3f3f;
int n;
int h[N],ne[N],e[N];
int dis[N];//i点到根节点的距离
int idx,root;
//父节点，子节点
void add(int x,int y)
{
e[idx]=y;
ne[idx]=h[x];
h[x]=idx++;
}
void dfs(int fa,int pre)
{
dis[fa]=dis[pre]+1;
int i,j;
for(i=h[fa];i!=-1;i=ne[i])
{
j=e[i];
dfs(j,fa);//父节点，子节点
}
}
void solve()
{
cin>>n;
int i,j;
memset(h,-1,sizeof(h));
for(i=1;i<=n;i++)
{
int x;
cin>>x;
if(x==-1)
root=i;
else
add(x,i);//i的父节点为x
}
dfs(root,0);
int ans=0;
vector<int>v;
for(i=1;i<=n;i++)
{
ans=max(ans,dis[i]);
}
for(i=1;i<=n;i++)
{
if(ans==dis[i])
{
v.push_back(i);
}
}
cout<<ans<<endl;
for(i=0;i<v.size();i++)
{
if(i!=v.size()-1)
cout<<v[i]<<' ';
else
cout<<v[i]<<endl;
}
}
signed main()
{
int t=1;
while(t--)
{
//快输
/*
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
*/
solve();
}
return 0;
}
2 spfa( )代码
#include<bits/stdc++.h>
#define endl '\n'
#define x first
#define y second
#define int long long
using namespace std;
typedef pair<int,int>PII;
const int N=2e5+10;
const int inf=0x3f3f3f3f;
int n;
int h[N],ne[N],e[N];
bool st[N];
int dis[N];//i点到根节点的距离
int idx,root;
//父节点，子节点
void add(int x,int y)
{
e[idx]=y;
ne[idx]=h[x];
h[x]=idx++;
}
void spfa()
{
//入队 true 出队false
int i,j;
queue<int>q;
memset(dis,0x3f,sizeof(dis));
dis[root]=1;
st[root]=true;
q.push(root);
while(q.size())
{
int t=q.front();
q.pop();
st[t]=false;
for(i=h[t];i!=-1;i=ne[i])
{
j=e[i];
if(dis[j]>dis[t]+1)
{
dis[j]=dis[t]+1;
}
if(!st[j])
{
q.push(j);
st[j]=true;
}
}
}
}
void solve()
{
cin>>n;
int i,j;
memset(h,-1,sizeof(h));
for(i=1;i<=n;i++)
{
int x;
cin>>x;
if(x==-1)
root=i;
else
add(x,i);//i的父节点为x
}
spfa();
int ans=0;
vector<int>v;
for(i=1;i<=n;i++)
{
ans=max(ans,dis[i]);
}
for(i=1;i<=n;i++)
{
if(ans==dis[i])
{
v.push_back(i);
}
}
cout<<ans<<endl;
for(i=0;i<v.size();i++)
{
if(i!=v.size()-1)
cout<<v[i]<<' ';
else
cout<<v[i]<<endl;
}
}
signed main()
{
int t=1;
while(t--)
{
//快输
/*
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
*/
solve();
}
return 0;
}
