先用tarjan缩点，再记忆话搜索一下
#include <stack>
#include <cstdio>
#include <cstring>
#include <iostream>
#define N 100001
#define min(x, y) ((x) < (y) ? (x) : (y)) int n, cnt, rp, tot, cnt1;
int head1[N], to1[N], next1[N], head[N], to[N], next[N], dfn[N], low[N], belong[N], ans[N], a[N];
bool ins[N];
std::stack <int> s; inline int read()
{
int x = 0, f = 1;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
return x * f;
} inline void add(int x, int y)
{
to[cnt] = y;
next[cnt] = head[x];
head[x] = cnt++;
} inline void add1(int x, int y)
{
to1[cnt1] = y;
next1[cnt1] = head1[x];
head1[x] = cnt1++;
} inline void tarjan(int u)
{
int i, v;
dfn[u] = low[u] = ++rp;
ins[u] = 1;
s.push(u);
for(i = head[u]; i ^ -1; i = next[i])
{
v = to[i];
if(!dfn[v])
{
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if(ins[v]) low[u] = min(low[u], dfn[v]);
}
if(low[u] == dfn[u])
{
tot++;
do
{
v = s.top();
s.pop();
ins[v] = 0;
belong[v] = tot;
} while(u ^ v);
}
} inline int dfs(int u)
{
int i, v;
if(ans[u])
return ans[u];
for(i = head1[u]; i ^ -1; i = next1[i])
{
v = to1[i];
ans[u] = dfs(v);
}
return ans[u] += a[u];
} int main()
{
int i, x, u, v;
memset(head, -1, sizeof(head));
memset(head1, -1, sizeof(head1));
n = read();
for(i = 1; i <= n; i++)
{
x = read();
add(i, x);
}
for(i = 1; i <= n; i++)
if(!dfn[i])
tarjan(i);
for(i = 1; i <= n; i++) a[belong[i]]++;
for(u = 1; u <= n; u++)
for(i = head[u]; i ^ -1; i = next[i])
{
v = to[i];
if(belong[u] ^ belong[v])
add1(belong[u], belong[v]);
}
for(i = 1; i <= n; i++)
printf("%d\n", dfs(belong[i]));
return 0;
}