记录编号	66496	评测结果	AAAAAAAATA
题目名称	[USACO Dec08] 奶牛的糖果	最终得分	90
用户昵称	隨風巽	是否通过	未通过
代码语言	C++	运行时间	3.256 s
提交时间	2013-07-29 17:04:28	内存使用	1.55 MiB

#include<iostream>
#include<fstream>
#include<cstdio>
#include<cstring>
using namespace std;
int N,i,next[100010],p=0,j,k,l,m,s[100010]={0},path[100010]={0},sc=0;
bool f[100010]={0};
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(s[i]==0)
	    {
			f[i]=true;
		    k=0;
			path[k++]=i;
			for(j=next[i];f[j]==false;j=next[j])   //找到环
		    {	
				f[j]=true;              //做标记
			    path[k++]=j;             //按先后顺序记录顶点
			}
			for(l=0;l<k;l++)
			{	
				s[path[l]]=k-l;            
				if(path[l]==j)break;     //查找切入点
			}
			sc=k-l;
			for(l;l<k;l++)
				s[path[l]]=sc;
		}
		memset(f,0,sizeof(f));
	}
	for(i=1;i<=N;i++)printf("%d\n",s[i]);
	return 0;
}