似乎没有答案为二元环的数据,例如这份代码能通过,但
5
2 1 4 5 3
就能卡掉
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n;
vector<int> e[N];
bool vis[N];
vector<int> path;
void dfs(int u, int fa, bool &flag, int &cyc) {
vis[u] = 1, path.emplace_back(u);
for (auto v : e[u]) {
if (vis[v]) {
if (flag || v == fa) continue;
flag = 1, cyc = 1;
for (int i = path.size() - 1; path[i] != v; i--) cyc++;
continue;
}
dfs(v, u, flag, cyc);
}
path.pop_back();
}
int main() {
cin >> n;
int ans = n;
for (int i = 1; i <= n; i++) {
int t;
cin >> t;
e[i].emplace_back(t);
e[t].emplace_back(i);
}
for (int i = 1; i <= n; i++) {
if (vis[i]) continue;
path.clear();
bool flag = 0;
int cyc = 0;
dfs(i, 0, flag, cyc);
ans = min(ans, cyc);
}
cout << ans;
return 0;
}