PTA L2-026 小字辈

Dear 丶 2023-02-12 15:27 8阅读 0赞

### PTA L2-026 小字辈 ###

*   *   *  题目
         *   *  AC代码

### 题目 ###

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

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

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

#### AC代码 ####

#include<bits/stdc++.h>
    using namespace std;
    const int MAXN = 1e6+5;
    vector<int> g[MAXN];
    vector<int> a;
    int ans;
    bool visit[MAXN];
    struct node{ 
    	int j,d;
    };
    queue<node> q; 
    
    void bfs(int j=0){ 
    	visit[j]=true;
    	q.push({ j,1});
    	node tmp;
    	int len,d,v;
    	while(!q.empty()){ 
    		tmp = q.front();
    		q.pop();
    		j = tmp.j;
    		len = g[j].size();
    		d = tmp.d;
    		for(int i=0;i<len;++i){ 
    			v = g[j][i];
    			if(!visit[v]){ 
    				visit[v]=true;
    				if(d>ans){ 
                        ans = d;
                        a.clear();
                    }
    				a.push_back(v);
    				q.push({ v,d+1});
    			}
    		}
    	}
    }
    
    int main(){ 
    	int n,d,t;
    	scanf("%d",&n);
    	for(int i=1;i<=n;++i){ 
    		scanf("%d",&d);
    		if(d==-1)d=0;//辈分最高的老祖宗不只有1个人，把他们指向0，便于处理遍历
    		g[i].push_back(d);
    		g[d].push_back(i);
    	}
    	bfs();
    	printf("%d\n",ans);
    	t = a.size()-1;
    	for(int i=0;i<t;++i)printf("%d ",a[i]);
    	printf("%d\n",a[t]);
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，8人围观）

还没有评论，来说两句吧...

相关阅读

相关 PTA:L2-014 列车调度

题目： [PTA | 程序设计类实验辅助教学平台千名教师建设，万道高质量题目，百万用户拼题的程序设计实验辅助教学平台![apple-touch-icon.png][]ht

梦里梦外;/ 2024年03月17日 17:04/ 0 赞/ 48 阅读

相关 PTA:L1-088 静静的推荐

题目： [https://pintia.cn/problem-sets/994805046380707840/exam/problems/1518582000729911

客官°小女子只卖身不卖艺/ 2024年03月16日 22:10/ 0 赞/ 18 阅读

相关小字辈

给定一个庞大家族的家谱，请你给出最小一辈的名单。输入格式：输入在第一行给出家族人口总数 N（不超过 100 000 的正整数） —— 简单起见，我们把家族成员从 1

太过爱你忘了你带给我的痛/ 2023年05月21日 07:17/ 0 赞/ 90 阅读

相关 PTA L2-026 小字辈

PTA L2-026 小字辈题目 AC代码题目本题给定一个庞大家族的家谱，要请你给出最小一辈的名单。输入格

Dear 丶/ 2023年02月12日 15:27/ 0 赞/ 9 阅读

相关 L2-026 小字辈 (25分)【天梯赛】

题目描述本题给定一个庞大家族的家谱，要请你给出最小一辈的名单。输入格式：输入在第一行给出家族人口总数 N（不超过 100 000 的正整数） —— 简单起见，我

ゝ一世哀愁。/ 2023年01月06日 11:39/ 0 赞/ 221 阅读

相关 L2-026 小字辈（25 分）

本题给定一个庞大家族的家谱，要请你给出最小一辈的名单。输入格式：输入在第一行给出家族人口总数 N（不超过 100 000 的正整数） ——简单起见，我们把家族成员从 1

柔情只为你懂/ 2022年05月23日 07:50/ 0 赞/ 205 阅读

相关 L2-026 小字辈

L2-026 小字辈（25 分）本题给定一个庞大家族的家谱，要请你给出最小一辈的名单。输入格式：输入在第一行给出家族人口总数 N（不超过 100 000 的正

太过爱你忘了你带给我的痛/ 2022年03月16日 12:18/ 0 赞/ 121 阅读

相关 PTA-L2-026 小字辈（25 分)

L2-026 小字辈（25 分) \[[L2-026 小字辈（25 分)][L2-026 _ _25]\] 本题给定一个庞大家族的家谱，要请你给出最小一辈的名单。

快来打我*/ 2022年02月27日 05:26/ 0 赞/ 254 阅读

相关 pta l2-2（链表去重）

题目链接：https://pintia.cn/problem-sets/994805046380707840/problems/994805072641245184 题意：给

我不是女神ヾ/ 2021年12月21日 01:03/ 0 赞/ 189 阅读

相关 PTA天梯 L3-007 天梯地图

L3-007 天梯地图题目：本题要求你实现一个天梯赛专属在线地图，队员输入自己学校所在地和赛场地点后，该地图应该推荐两条路线：一条是最快到达路线；一条是最短距离

柔情只为你懂/ 2021年12月20日 06:15/ 0 赞/ 363 阅读