小字辈[天梯赛]

题目描述

思路

深度优先搜索

具体流程
1.读入每个人的祖先，标记辈分最高的老祖宗对应的下标pos
2.从pos开始dfs，每次判断当前遍历的深度，如果>原来的深度，更新，并将存储最小辈分的数组清零；如果=原来深度，则将当前的人加入数组；之后继续搜索该人对应的孩子

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
vector<int> v[N];
vector<int> res;
int cnt = -1;
void dfs(int x, int step)
{if(step > cnt){cnt = step;res.clear();}if(step == cnt) res.push_back(x);for(int i = 0; i < v[x].size(); i ++) dfs(v[x][i], step + 1); return;
}
int main()
{int n, pos;cin >> n;for(int i = 1; i <= n; i ++){int x;cin >> x;if(x == -1) pos = i;else v[x].push_back(i);}dfs(pos, 1);cout << cnt << endl;for(int i = 0; i < res.size(); i ++){if(i != res.size() - 1) cout << res[i] << " ";else cout << res[i] << endl;}return 0;
}