本题给定一个庞大家族的家谱, 要请你给出最小一辈的名单.
输入格式:
输入在第一行给出家族人口总数 N(不超过 100 000 的正整数) -- 简单起见, 我们把家族成员从 1 到 N 编号. 随后第二行给出 N 个编号, 其中第 i 个编号对应第 i 位成员的父 / 母. 家谱中辈分最高的老祖宗对应的父 / 母编号为 -1. 一行中的数字间以空格分隔.
输出格式:
首先输出最小的辈分 (老祖宗的辈分为 1, 以下逐级递增). 然后在第二行按递增顺序输出辈分最小的成员的编号. 编号间以一个空格分隔, 行首尾不得有多余空格.
输入样例:
- 9
- 2 6 5 5 -1 5 6 4 7
输出样例:
4
1 9
主要思路:
将 i 的所有儿 / 女存入容器 v [ i ] 中, dfs, 注意 dfs 内不能用迭代器访问容器, 只能用下标访问.
- #include<iostream>
- #include<vector>
- #include<algorithm>
- using namespace std;
- vector<int>v[100005],ans;//v[i] 存入 i 的儿女编号, ans 存入最小辈分编号
- vector<int>::iterator it;
- int maxd;
- void dfs(int n,int deep)
- {
- int i;
- for (i=0;i<v[n].size();i++)
- dfs(v[n][i],deep+1);
- if (deep>maxd)
- {
- maxd=deep;
- ans.clear();
- ans.push_back(n);
- }
- else if (maxd==deep)
- ans.push_back(n);
- }
- int main()
- {
- int n,i,t,pos;
- cin>>n;
- for (i=1;i<=n;i++)
- {
- cin>>t;
- if (t==-1)
- {
- pos=i;
- continue;
- }
- v[t].push_back(i);
- }
- dfs(pos,1);
- sort(ans.begin(),ans.end());
- cout<<maxd<<endl;
- cout<<*ans.begin();
- for (it=ans.begin()+1;it!=ans.end();it++)
- cout<<' '<<*it;
- cout<<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3004806.html