PTA L2-026 小字辈

Dear 丶 2023-02-12 15:27 21阅读 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;
    }