对于一个牛，它存在两种状态：1.处于联通分量 2.不处于联通分量。对于处于联通分量的牛，求出联通分量的大小；对于不处于联通分量的牛，求出其距离联通分量的路程+联通分量大小。
不同的联通分量，染上不同的颜色，可以计算各个联通分量的大小。
#include<bits/stdc++.h>
using namespace std; int vis[];
int low[];
int Loop[],color[],dfn[],head[],ans[],st[], Next[];
int pos;
int k=;
int col;
int top; struct node
{
int v,next;
}edge[]; void Add(int u,int v)
{
edge[k].v = v;
edge[k].next = head[u];
head[u] = k++;
} void Find(int root,int x,int step)
{
if(ans[x]!=)
{
ans[root] = ans[x]+step;
return;
}
else
Find(root,Next[x],step+);
} void Tarjan(int u)
{
dfn[u] = low[u] = ++pos;
st[++top] = u;
vis[u] = ;
for(int i=head[u];i!=-;i=edge[i].next)
{
int v = edge[i].v;
if(!dfn[v])
{
Tarjan(v);
low[u] = min(low[u],low[v]);
}
else if(vis[v])
{
low[u] = min(low[u],dfn[v]);
}
}
if(dfn[u] == low[u])
{
col++;
int x;
do{
x = st[top--];
vis[x] = ;
color[x] = col;
}while(x!=u);
}
} int main()
{
memset(head,-,sizeof(head));
int n,v;
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",&v);
Next[i] = v;
Add(i,v);
if(v==i)
ans[i] = ;
}
for(int i=;i<=n;i++)
{
if(!dfn[i])
{
Tarjan(i);
}
}
for(int i=;i<=n;i++)
{
Loop[color[i]]++;
}
for(int i=;i<=n;i++)
{
if(Loop[color[i]]!=)
ans[i] = Loop[color[i]];
}
for(int i=;i<=n;i++)
{
if(ans[i]==)
Find(i,Next[i],);
}
for(int i=;i<=n;i++)
{
printf("%d\n",ans[i]);
}
return ;
}