裸的DFS
比賽的時候沒想出來 血虧 后面用stack寫了個
https://pintia.cn/problem-sets/994805046380707840/problems/994805055679479808
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <sstream>
#include <algorithm>
int N, M;
//const int MAXN = , MAXM = 0;
//typedef long long ll;
const int si =100000;
using namespace std;
int par[si];
int rankk[si];
vector<int> v;
stack<int> stk;
int maxx = 0;
void solve(int rt) {
int p = rt;
while (!rankk[p]) {
stk.push(p);
p = par[p];
}
int it = rankk[p];
int x = 1;
while (!stk.empty()) {
x = stk.top(); stk.pop();
rankk[x] = ++it;
}
maxx = max(rankk[x], maxx);
}
int main() {
cin >> N;
int rt = 0;
for (int i = 1; i <= N; i++) {
scanf("%d", &par[i]);
if (par[i] == -1) rt = i;
}
//solve
rankk[rt] = 1;
for (int i = 1; i <= N; i++) {
solve(i);
}
//output
for (int i = 1; i <= N; i++) {
if (rankk[i] == maxx)
v.push_back(i);
}
cout << maxx << endl;
for (int i = 0; i < v.size() - 1; i++) {
printf("%d ", v[i]);
}
printf("%d", v[v.size() - 1]);
cout << endl;
return 0;
}
