L2-026 小字辈

第一眼想到的是BFS,然后就用BFS,个人感觉还是有一丢丢麻烦。

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<vector<int>> vec;
int main() {
	int n;
	cin >> n;
	vec.resize(n+10);
	int root = 0;
	for (int i = 1; i <= n; i++) {
		int parent;
		cin >> parent;
		if (parent != -1) {
			vec[parent].push_back(i);
		}
		else {
			root = i;
		}
	}
	int pcnt = 0;
	int level = 0;
	set<int> res;
	queue<int> v;
	v.push(root);
	int flag = 0;
	while (!v.empty()) {
		int left = v.size();//left=2
		if (pcnt + left >= n) {//需要将这一次弹出来的全部记录下来
			flag = 1;
		}
		level++;
		for (int i = 0; i < left; i++) {
			int parent = v.front();
			v.pop();
			if (flag) res.insert(parent);
			++pcnt;//弹出加一
			for (int j = 0; j < vec[parent].size(); j++) {
				v.push(vec[parent][j]);
			}
		}
	}
	cout << level << endl;
	for (set<int>::iterator it = res.begin(); it != res.end();) {
		cout << *it;
		if (++it != res.end()) cout << " ";
	}
	return 0;
}