记录编号	127925	评测结果	AAAAAAAAAA
题目名称	[USACO Dec08] 奶牛的糖果	最终得分	100
用户昵称	乌龙猹	是否通过	通过
代码语言	C++	运行时间	0.164 s
提交时间	2014-10-16 16:53:21	内存使用	1.53 MiB

#include<cstdio>
using namespace std;
int n;
int f[100001],to[100001],o[100001];
bool bo[100001];
int dfs(int,int);
int main()
{
	freopen("treat.in","r",stdin);
	freopen("treat.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&to[i]);
	for(int i=1;i<=n;i++)
	{
		f[i]=dfs(i,1);
		printf("%d\n",f[i]);
	}
	return 0;
}
int dfs(int k,int d)
{
	if(f[k]) return f[k];
	bo[k]=1;
	o[k]=d;
	if(!bo[to[k]] || f[to[k]])
	{
		int sum=dfs(to[k],d+1);
		if(!f[k]) f[k]=sum+1;
	}
	else
	{
		f[k]=o[k]-o[to[k]]+1;
		int x=to[k];
		while(x!=k)
		{
			f[x]=f[k];
			x=to[x];
		}
	}
	return f[k];
}