记录编号	112821	评测结果	AAAAAAAAAA
题目名称	[USACO Dec08] 奶牛的糖果	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	1.016 s
提交时间	2014-07-17 10:26:08	内存使用	1.45 MiB

#include<fstream>
using namespace std;
int s,g[100003],nh[100003]={0},oh[100003]={0};
void dfs(int i);
int main()
{
	ifstream fi("treat.in");
	ofstream fo("treat.out");
	int n;
	fi>>n;
	for(int i=1;i<=n;i++)
		fi>>g[i];
	for(int i=1;i<=n;i++)
		if(!oh[i])
			dfs(i);
	for(int i=1;i<=n;i++)
		fo<<oh[i]<<endl;
	return 0;
}
void dfs(int i)
{
	int k=i,l=0;
	while(!nh[k]&&!oh[k])
	{
		l++;
		nh[k]=l;
		k=g[k];
	}
	if(oh[k])
		l+=oh[k];
	else
	{
		int ll=l+1-nh[k];
		while(!oh[k])
		{
			oh[k]=ll;
			k=g[k];
		}
	}
	k=i;
	while(!oh[k])
	{
		oh[k]=l;
		l--;
		k=g[k];
	}		
}