最小环求解采用并查集求最小环。
只适用于本题的情况。对于新加可以使得两个子树合并的边，总有其中一点为其中一棵子树的根。
复杂度 \(O(n)\) 。
#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 200005;
int f[maxn], dist[maxn];
int n, to, ans;
int father(int x)
{
if(f[x] != x){
int tmp = f[x];
f[x] = father(f[x]);
dist[x] += dist[tmp];
}
return f[x];
}
void solve(int a, int b)
{
int af = father(a), bf = father(b);
if(af == bf){
ans = min(ans, dist[a] + dist[b] + 1);
}
else{
f[af] = bf;
dist[a] = dist[b] + 1;
}
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++) f[i] = i;
ans = inf;
for(int i = 1; i <= n; i++){
scanf("%d", &to);
solve(i, to);
}
printf("%d\n", ans);
return 0;
}