记录编号	73603	评测结果	AAAAAAAAAA
题目名称	[USACO Dec08] 奶牛的糖果	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	0.179 s
提交时间	2013-10-22 10:10:16	内存使用	3.48 MiB

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
int N,next[100001],num[100001],go[100001],newcir[100001];
void dfs(int x)
{
	int k=x,deep=0;
	while(!newcir[k]&&!go[k])//没有找到  新环  也没有找到  旧环(链)
	{
		deep++;
		newcir[k]=deep;
		k=next[k];
	}
	if(go[k])//有旧环(链) 此时go[k]即这个环的长度
		deep+=go[k];
	else//新环 此时k为第一次进入环的节点
	{
		int cir=deep+1-newcir[k];
		while(!go[k])//环上点都能绕cir的长度
		{
			go[k]=cir;
			k=next[k];
		}
	}
	k=x;
	while(!go[k])//计算链上节点
	{
		go[k]=deep;
		deep--;
		k=next[k];
	}
}
int main()
{
	freopen("treat.in","r",stdin);
	freopen("treat.out","w",stdout);
	memset(go,0,sizeof(go));
	memset(num,0,sizeof(num));
	memset(newcir,0,sizeof(newcir));
	scanf("%d",&N);
	int i;
	for(i=1;i<=N;i++)
	{
		scanf("%d",&next[i]);
		num[next[i]]++;
	}
	for(i=1;i<=N;i++)
		if(!go[i])
		{
			dfs(i);
		}
	for(i=1;i<=N;i++)printf("%d\n",go[i]);
	return 0;
}