只需枚举前 97 个同学并 dfs 求最小环即可通过,如这份代码:
#include <bits/stdc++.h>
using namespace std;
int f[200010];
int dfn[200010];
int cnt = 0;
int ans = INT_MAX;
void dfs(int x) {
dfn[x] = ++cnt;
int y = f[x];
if (dfn[y]) {
ans = min(ans, dfn[x] - dfn[y] + 1);
return ;
}
dfs(y);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> f[i];
}
for (int i = 1; i <= min(n, 97); i++) {
cnt = 0;
for (int i = 1; i <= n; i++) {
dfn[i] = 0;
}
dfs(i);
}
cout << ans << "\n";
return 0;
}
提交记录
建议添加一组数据为多组三元环中靠后的位置添加一组二元环,类似于:
n
2 3 1 5 6 4 ... (i+1) i ... (n-1) n (n-2)