本题给定一个庞大家族的家谱，要请你给出最小一辈的名单。
输入格式：
输入在第一行给出家族人口总数 N（不超过 100 000 的正整数） —— 简单起见，我们把家族成员从 1 到 N 编号。随后第二行给出 N 个编号，其中第 i 个编号对应第 i 位成员的父/母。家谱中辈分最高的老祖宗对应的父/母编号为 -1。一行中的数字间以空格分隔。
输出格式：
首先输出最小的辈分（老祖宗的辈分为 1，以下逐级递增）。然后在第二行按递增顺序输出辈分最小的成员的编号。编号间以一个空格分隔，行首尾不得有多余空格。
输入样例：
9
2 6 5 5 -1 5 6 4 7
输出样例：
4
1 9
终于AC了，一波三折啊。
比赛的时候用 队列+set 水到15分，回来自己按照比赛的思路敲了下16分。下面是代码：
//Asimple
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = + ;
int n, m, res, ans, len, T, k, num, sum, t, cnt;
bool vis[maxn];
struct node{
int fa;
};
node a[maxn]; void input() {
ios_base::sync_with_stdio(false);
cin >> n;
queue<int> q;
for(int i=; i<=n; i++) {
cin >> num;
a[i].fa = num;
if( num == - ) {
q.push(i);
vis[i] = true;
} else vis[i] = false;
}
set<int> S;
int cas = ;
while( !q.empty() ) {
S.clear();
while( !q.empty() ) {
S.insert(q.front());
q.pop();
}
cas ++;
for(int i=; i<=n; i++) if( !vis[i] ) {
if( S.count(a[i].fa) == ) {
q.push(i);
}
}
}
cout << cas << endl;
bool f = true;
set<int>::iterator it;
for(it=S.begin(); it!=S.end(); it++) {
if( f ) f = false;
else cout << " ";
cout << *it;
}
cout << endl;
} int main(){
input();
return ;
}
emmmm，然后想了下是不是set的原因时间超限，然后直接用vector保存各个辈分的人。然后15分。。。╮(╯▽╰)╭ 代码：
//Asimple
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = + ;
int n, m, res, ans, len, T, k, num, sum, t, cnt;
struct node{
int fa;
};
node a[maxn];
vector<int> re[maxn]; void input() {
ios_base::sync_with_stdio(false);
cin >> n;
queue<int> q;
len = ;
for(int i=; i<=n; i++) {
cin >> num;
a[i].fa = num;
if( num == - ) {
q.push(i);
re[len].push_back(i);
}
} while( !q.empty() ) {
len ++;
int T = q.size();
while( T -- ) {
int now = q.front(); q.pop();
for(int i=; i<=n; i++) {
if( a[i].fa == now ) {
q.push(i);
re[len].push_back(i);
}
}
} }
cout << len << endl;
for(int i=; i<re[len-].size(); i++) {
if( i!= ) cout << " ";
cout << re[len-][i];
}
cout << endl;
} int main(){
input();
return ;
}
仔细看了下代码，发现自己的BFS每次都要从1循环到n，emmmm，好像挺浪费时间的，不如把关系也用vector存吧，至少每次不用循环那么多次。一交20分。
好像去年有道题目也是被vector坑了，今天还是没有想到vector。真的傻啊。
20分代码：
//Asimple
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = + ;
int n, m, res, ans, len, T, k, num, sum, t, cnt;
vector<int> a[maxn];
vector<int> re[maxn]; void input() {
ios_base::sync_with_stdio(false);
cin >> n;
queue<int> q;
len = ;
for(int i=; i<=n; i++) {
cin >> num;
a[num].push_back(i);
if( num == - ) {
q.push(i);
re[len].push_back(i);
}
} while( !q.empty() ) {
len ++;
int T = q.size();
while( T -- ) {
int now = q.front(); q.pop();
for(int i=; i<a[now].size(); i++) {
q.push(a[now][i]);
re[len].push_back(a[now][i]);
}
}
} cout << len << endl;
for(int i=; i<re[len-].size(); i++) {
if( i != ) cout << " ";
cout << re[len-][i];
}
cout << endl;
} int main(){
input();
return ;
}