记录编号	187891	评测结果	AAAAAAAAAA
题目名称	[USACO Dec08] 奶牛的糖果	最终得分	100
用户昵称	赵日天	是否通过	通过
代码语言	C++	运行时间	0.142 s
提交时间	2015-09-21 00:00:53	内存使用	2.39 MiB

#include <cstdio>
//----------------------------------------------------
int  n;
int  i,j,k;

int  next[110000];

int  che[110000];
int  set[110000];
int  sta[110000],tai;

int  ans[110000];
//----------------------------------------------------
int  main( )
{
	freopen( "treat.in"  , "r" , stdin  );
	freopen( "treat.out" , "w" , stdout );
	scanf("%d",&n);
	for (i=1; i<=n; i++)
		scanf("%d",&next[i]);
	for (i=1; i<=n; i++)
	if (!ans[i])
	{
		for (j=i+(tai=0); !che[j]; j=next[j])
		{
			che[j]=1;
			set[j]=++tai;
			sta[tai]=j;
		}
		if (ans[j])
			for (ans[sta[tai]]=ans[j]+1; --tai; )
				 ans[sta[tai]]=ans[sta[tai+1]]+1;	
		else
		{
			for (k=tai; k>=set[j]; k--)
				ans[sta[k]]=tai-set[j]+1;
			for (; k; k--)
				ans[sta[k]]=ans[sta[k+1]]+1;
		}
	}
	for (i=1; i<=n; i++)
		printf("%d\n",ans[i]);
}