题目
本题给定一个庞大家族的家谱，要请你给出最小一辈的名单。
输入格式：
输入在第一行给出家族人口总数 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 |
代码：
1 | |
2 | using namespace std; |
3 | int n,m,root,sum=-1; |
4 | vector<int> f[110000],ans; |
5 | void dfs(int x,int cnt){ |
6 | if(f[x].size()==0 && cnt>sum){ |
7 | sum=cnt; |
8 | ans.clear(); |
9 | } |
10 | if(sum==cnt){ |
11 | ans.push_back(x); |
12 | } |
13 | for(int i=0;i<f[x].size();i++){ |
14 | dfs(f[x][i],cnt+1); |
15 | } |
16 | } |
17 | int main(){ |
18 | scanf("%d",&n); |
19 | for(int i=1;i<=n;i++){ |
20 | scanf("%d",&m); |
21 | if(m==-1) |
22 | root=i; |
23 | else |
24 | f[m].push_back(i); |
25 | } |
26 | dfs(root,1); |
27 | printf("%d\n",sum); |
28 | for(int i=0;i<ans.size();i++){ |
29 | if(i==0){ |
30 | printf("%d",ans[i]); |
31 | } |
32 | else{ |
33 | printf(" %d",ans[i]); |
34 | } |
35 | } |
36 | return 0; |
37 | } |