记录编号 66818 评测结果 AAAAAAAATA
题目名称 [USACO Dec08] 奶牛的糖果 最终得分 90
用户昵称 Gravatar老师好~~~ 是否通过 未通过
代码语言 C++ 运行时间 2.467 s
提交时间 2013-08-02 11:08:21 内存使用 4.52 MiB
显示代码纯文本
#include<fstream>
using namespace std;
ifstream fin("treat.in");
ofstream fout("treat.out");
int c,cx,cd;
int a[100001],ans[100001],path[100001];
bool b[100001]={0};
void dfs(int x,int step)
{
	if(b[x]==1)
	{
		c=1;//c表示是否在环中,cx记录环点,cd记录长度
		cx=x;
		cd=1;
		int k=step;
		while(path[k]!=x)
		{
			k--;
			cd++;
		}
		ans[x]=cd;//寻找在环中的结点的长度
	}
	else
	{
		b[x]=1;
		path[step+1]=x;
		dfs(a[x],step+1);
		if(x==cx)
			c=0;
		else
		{
			if(c==1)
				ans[x]=cd;
			else
				ans[x]=++cd;
		}
	}//环外的结点的长度
}
int main()
{
	int n,j,i;
    fin>>n;
    for(i=1;i<=n;i++)
		fin>>a[i];
	for(i=1;i<=n;i++)
	{
		if(ans[i]==0)
		{
			for(j=1;j<=n;j++)
				b[j]=0;
			c=0;
			dfs(i,0);
		}
	}
	for(i=1;i<=n;i++)
		fout<<ans[i]<<endl;
	return 0;
}