记录编号	126839	评测结果	AAAAAAAAAA
题目名称	[USACO Dec08] 奶牛的糖果	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.135 s
提交时间	2014-10-14 12:11:41	内存使用	1.55 MiB

//stack的模拟
//记忆化搜索 

#include<iostream>
#include<cstdio>
using namespace std;
int tu[100010]={0},nz[100010]={0},zhi[100010]={0},n,zj1,zj2,zj3,i,p;
bool pan[100010]={0};
void init()
{
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d",&tu[i]);
}
void A_find()
{
	for(i=1;i<=n;i++)
	if(!pan[i])//没有判断过 
	{
		nz[0]=1;nz[1]=i;//栈初始化 
		pan[i]=true;//标记 
		zj1=i;
		while(!pan[ tu[zj1] ])//遇到判断过的点后跳出 
		{
			nz[0]++;//计数 
			nz[ nz[0] ]=tu[zj1];//入栈 
			zj1=tu[zj1];
			pan[zj1]=true;
		}
		//假如有标记但无值，代表栈里面环的存在 ， 
		if(zhi[ tu[zj1] ])//无环 
		{
			zj1=zhi[ tu[zj1] ];
			zj2=nz[0];
			while(zj2)//栈里元素依次出栈赋值 
			{
				zj1++;
				zhi[ nz[zj2] ]=zj1;
				zj2--;
			}
		}
		else
		{
			zj1=tu[zj1];zj2=nz[0];zj3=1;//寻找环 
			while(nz[zj2]!=zj1){zj3++;zj2--;}//找到环起始点，跳出 
			for(p=zj2;p<=nz[0];p++)zhi[ nz[p] ]=zj3;//环的赋值 
			zj2--;
			while(zj2)//栈里元素依次出栈赋值 
			{
				zhi[ nz[zj2] ]=++zj3;
				zj2--;
			}
		}
	}
}
void End_answer()
{
	for(i=1;i<=n;i++)printf("%d\n",zhi[i]);
}
int main()
{
	freopen("treat.in","r",stdin);
	freopen("treat.out","w",stdout);
	init();
	A_find();
	End_answer();
	return 0;
}