题义抽象出来就是一道用并查集维护最小环的题。
我们在这里除了一个并查集数组外,还开了一个环距离数组,可不进行初始化,在最后面的结果加一即可。
相较于传统并查集的写法,我们这里还要维护其父链的长度。每次找到环更新一次答案。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200001;
int n;
int uni[MAXN];
int dist[MAXN];
int ans = 0x8F8F8F;
int find(int x) {
if ( uni[x] == x )
return x;
int father = uni[x];
uni[x] = find(uni[x]);
dist[x] += dist[father];
return uni[x];
}
void solve(int a, int b) {
int u = find(a);
int v = find(b);
if ( u != v ) {
uni[u] = v;
dist[a] = dist[b] + 1;
} else {
ans = min(ans, dist[a] + dist[b] + 1);
}
}
int main() {
ios::sync_with_stdio(false);
cin >> n;
for ( int i = 1; i <= n; ++i )
uni[i] = i;
int cur;
for ( int i = 1; i <= n; ++i ) {
cin >> cur;
solve(i, cur);
}
cout << ans << endl;
return 0;
}