题解一：

#include <bits/stdc++.h>
const int N = 1e5 + 5;
using namespace std;
int a[N], dep[N], ans[N];
void dfs(int x, int l) {
    if (ans[x]) return;
    if (dep[x]) {
        ans[x] = dep[l] + 1 - dep[x];
        int p = a[x];
        while (p != x) {
            ans[p] = ans[x];
            p = a[p];
        }
        return;
    }
    dep[x] = dep[l] + 1;
    dfs(a[x], x);
    if (!ans[x]) ans[x] = ans[a[x]] + 1;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) if (!dep[i]) dfs(i, 0);
    for (int i = 1; i <= n; i++) cout << ans[i] << "\n";
    return 0;
}

题解二：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector<int> G1[N], G2[N];
int tsp, cnt, dfn[N], low[N], scc[N], num[N], f[N];
stack<int> stk;
bool instk[N];
void tarjan(int x) {
    dfn[x] = low[x] = ++tsp;
    stk.push(x);
    instk[x] = 1;
    for (int y : G1[x]) {
        if (!dfn[y]) {
            tarjan(y);
            low[x] = min(low[x], low[y]);;
        } else if (instk[y]) {
            low[x] = min(low[x], dfn[y]);
        }
    }
    if (dfn[x] == low[x]) {
        cnt++;
        for (int z = -1; z != x;) {
            z = stk.top();
            stk.pop();
            instk[z] = 0;
            scc[z] = cnt;
            num[cnt]++;
        }
    }
}
int dfs2(int x) {
    if (f[x]) return f[x];
    f[x] = num[x];
    for (int i : G2[x]) f[x] += dfs2(i);
    return f[x];
}
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1, x; i <= n; i++) scanf("%d", &x), G1[i].push_back(x);
    tsp = cnt = 0;
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    memset(instk, 0, sizeof(instk));
    memset(scc, 0, sizeof(scc));
    memset(num, 0, sizeof(num));
    for (int i = 1; i <= n; i++) if (dfn[i] == 0) tarjan(i);
    map<pair<int, int>, bool> mp;
    vector<int> rd(cnt + 1);
    for (int i = 1; i <= n; i++) for (int j : G1[i]) {
        int x = scc[i], y = scc[j];
        if (x != y && !mp[{x, y}]) G2[x].push_back(y), rd[y]++, mp[{x, y}] = 1;
    }
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= cnt; i++) if (rd[i] == 0) dfs2(i);
    for (int i = 1; i <= n; i++) printf("%d\n", f[scc[i]]);
    return 0;
}

#include<bits/stdc++.h>
const int N=1e5+5;
using namespace std;
int a[N],dep[N],ans[N];
void dfs(int x,int l){
    if(ans[x])return;
    if(dep[x]){
        ans[x]=dep[l]+1-dep[x];
        int p=a[x];
        while(p!=x){
            ans[p]=ans[x];
            p=a[p];
        }
        return;
    }
    dep[x]=dep[l]+1;
    dfs(a[x],x);
    if(!ans[x])ans[x]=ans[a[x]]+1;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)if(!dep[i])dfs(i,0);
    for(int i=1;i<=n;i++)cout<<ans[i]<<"\n";
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<int>G1[N],G2[N]; 
int tsp,cnt,dfn[N],low[N],scc[N],num[N],f[N];
stack<int> stk;bool instk[N];
void tarjan(int x)
{
    dfn[x]=low[x]=++tsp;
    stk.push(x);instk[x]=1;
    for(int y:G1[x])
    {
        if(!dfn[y])
        {
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(instk[y])low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x])
    {
        cnt++;
        for(int z=-1;z!=x;)
        {
            z=stk.top();stk.pop();instk[z]=0;
            scc[z]=cnt;
            num[cnt]++;
        }
    }
}
int dfs2(int x)
{
    if(f[x])return f[x];
    f[x]=num[x];
    for(int i:G2[x])f[x]+=dfs2(i);
    return f[x];
}
int main()
{
    int n;scanf("%d",&n);
    for(int i=1,x;i<=n;i++)scanf("%d",&x),G1[i].push_back(x);
    tsp=cnt=0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));
    memset(instk,0,sizeof(instk));
    memset(scc,0,sizeof(scc));
    memset(num,0,sizeof(num));
    for(int i=1;i<=n;i++)if(dfn[i]==0)tarjan(i);
    map<pair<int,int>,bool>mp; vector<int>rd(cnt+1);
    for(int i=1;i<=n;i++)for(int j:G1[i])
    {
        int x=scc[i],y=scc[j];
        if(x!=y && !mp[{x,y}])G2[x].push_back(y),rd[y]++,mp[{x,y}]=1;
    }
    memset(f,0,sizeof(f));
    for(int i=1;i<=cnt;i++)if(rd[i]==0)dfs2(i);
    for(int i=1;i<=n;i++)printf("%d\n",f[scc[i]]);
    return 0;
}