记录编号	527600	评测结果	AAAAAAAAAA
题目名称	[USACO Dec08] 奶牛的糖果	最终得分	100
用户昵称	HZOI_RXR	是否通过	通过
代码语言	C++	运行时间	0.980 s
提交时间	2019-02-17 21:12:46	内存使用	6.78 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
#define maxn 100050
int to[maxn],low[maxn],dfn[maxn],belong[maxn],stack[maxn],cirl[maxn],reto[maxn],candy[maxn],in[maxn];
bool vis[maxn],v[maxn];
int n,m,top,cnt,ind;
void tarjan(int u)
{
	dfn[u]=low[u]=++ind;
	vis[u]=1;
	stack[++top]=u;
	int end=to[u];
	if(!dfn[end])tarjan(end),low[u]=min(low[u],low[end]);
	else if(vis[end])low[u]=min(low[u],dfn[end]);
	if(dfn[u]==low[u])
	{
		
		int t;
		cnt++;
		do
		{
			t=stack[top--];
			cirl[cnt]++;
			belong[t]=cnt;
			vis[t]=0;
		}while(t!=u);
	}
}
void dfs(int x)
{
	if(candy[x])return ;
	v[x]=1;
	int t=reto[x];//cout<<111<<endl;
	if(t)dfs(t);
	
	if(!t)candy[x]=max(candy[x],cirl[x]);    
	else 
	candy[x]=max(candy[x],candy[t]+cirl[x]);


}
int main()
{
	freopen("treat.in","r",stdin);
	freopen("treat.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)scanf("%d",&to[i]);
	for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
	for(int i=1;i<=n;i++)
	if(belong[i]!=belong[to[i]])reto[belong[i]]=belong[to[i]];
	for(int i=1;i<=cnt;i++)if(!v[i])dfs(i);
	for(int i=1;i<=n;i++)cout<<candy[belong[i]]<<endl;
}