如下所示的程序，采用了没有路径压缩的并查集做法，理论最坏复杂度为 $O(n^2)$，但能通过现有的所有测试数据，因此针对这一错误做法进行hack

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
constexpr int maxn = 1e5+10;
int n,a[maxn],fa[maxn],ans[maxn];
int query(int x) {
    if(fa[x] == x) return x;
    return query(fa[x]);
}
void dfs(int x, int y) {
    int a = query(x), b = query(y);
    if(a == b) {        // found cycle
        int ct = 1;
        for(int i=y;i!=x;i=fa[i]) ct++;
        for(int i=y;i!=x;i=fa[i]) ans[i] = ct;
        ans[x] = ct;
    }else{
        fa[x] = y;
    }
}
int main() {
    // freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin >> n;
    for(int i=1;i<=n;i++)
        fa[i] = i;
    for(int i=1;i<=n;i++) {
        cin >> a[i];
        dfs(i, a[i]);
    }
    for(int i=1;i<=n;i++) {
        if(!ans[i]) {
            int ct=0, j=i;
            for(;!ans[j];j=fa[j])
                ct++;
            ans[i] = ans[j] + ct;
        }
    }
    for(int i=1;i<=n;i++)
        cout << ans[i] << endl;
    return 0;
}

数据生成代码如下：

#include <iostream>
using namespace std;
int main() {
    freopen("in.txt", "w", stdout);
    int n = 1e5;
    cout << n << endl;
    cout << n << " ";
    for(int i=1;i<=n-1;i++)
        cout << i << " ";
    cout << endl;
    return 0;
}