PAT 7-7 小字辈 (25 分)
小白入门不懂BFS(广度优先搜索)和DFS(深度优先搜索),如果不懂请参考原作者这里
-------------------------------https://blog.csdn.net/raphealguo/article/details/7523411--------------------------------------------------------
本题给定一个庞大家族的家谱,要请你给出最小一辈的名单。
输入格式:
输入在第一行给出家族人口总数 N(不超过 100 000 的正整数) —— 简单起见,我们把家族成员从 1 到 N 编号。随后第二行给出 N 个编号,其中第 i 个编号对应第 i 位成员的父/母。家谱中辈分最高的老祖宗对应的父/母编号为 -1。一行中的数字间以空格分隔。
输出格式:
首先输出最小的辈分(老祖宗的辈分为 1,以下逐级递增)。然后在第二行按递增顺序输出辈分最小的成员的编号。编号间以一个空格分隔,行首尾不得有多余空格。
输入样例:
9
2 6 5 5 -1 5 6 4 7
输出样例:
4
1 9
最初思路:最开始有思路 如下图,尝试用vector写,但是发现解决不了不断搜索的问题,如果非要去暴力搜索,貌似超级麻烦;
这次收获挺大,一直不懂bfs和dfs,这次也系统的看了一下,一会儿再去搞两道练习一下;
最终思路:我的最初思路,和我的画的图都是没问题的!看了一下网上大牛的解题方法,用到了图的bfs(广度优先搜索),然后就学习了一下,还利用了队列!
步骤:
1,我们把输入的数据利用vector储存,如图,为我们后续步骤做基础!在输入期间标记老祖宗的下标(一开始就想到的)
2,我们创建一个数组,这个数组的用处就是标记每个人的辈分,最终,利用这个辈分找到我们所要的最小辈分(数是最大值),这里我们先把老祖宗的辈分设为1,即:int vv[100005]; vv[lzz]=1;
3, 我们先把老祖宗的下标入队,看老祖宗这哥数组有几个元素,如图2,利用向下搜索。如图3;并且不断更新最小辈的值;
#include<iostream>
#include<vector>
#include<cstdio>
#include<set>
#include<map>
#include<string>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stdlib.h>
#include<ctype.h>
#include<stack>
#include<queue>
#include<list>
using namespace std;
vector<int>v[200005];
int vv[100005];
queue<int>q;
int main(){
int n,x,lzz;//lzz 记录老祖宗
scanf("%d",&n);
if(n==1){
}
for(int i=1; i<=n; i++){
scanf("%d",&x);
if(x==-1)
lzz=i;
else
v[x].push_back(i);
}
if(n==1){
printf("%d\n%d",1,1);
return 0;
}
q.push(lzz);
int bfen=1; //统计辈分
vv[lzz]=1;
while(!q.empty()){
int temp = q.front();
q.pop();
for(int i=0;i<v[temp].size();i++){
vv[v[temp][i]] = vv[temp]+1;//更新每个人的辈分
bfen = max(bfen,vv[v[temp][i]]);//更新(获得)最小辈分的值
q.push(v[temp][i]);//把下一次要遍历的入队
}
}
printf("%d\n",bfen);
int flag = 0;
for(int i=1;i<=n;i++){
if(vv[i]==bfen){
if(!flag){
printf("%d",i);
flag = 1;
}
else
printf(" %d",i);
}
}
}