P2921 在农场万圣节Trick or Treat on the Farm 并查集

P2921 [USACO08DEC]在农场万圣节Trick or Treat on the Farm

题目描述

每年，在威斯康星州，奶牛们都会穿上衣服，收集农夫约翰在N(1<=N<=100，000)个牛棚隔间中留下的糖果，以此来庆祝美国秋天的万圣节。

由于牛棚不太大，FJ通过指定奶牛必须遵循的穿越路线来确保奶牛的乐趣。为了实现这个让奶牛在牛棚里来回穿梭的方案，FJ在第i号隔间上张贴了一个“下一个隔间”Next_i(1<=Next_i<=N)，告诉奶牛要去的下一个隔间；这样，为了收集它们的糖果，奶牛就会在牛棚里来回穿梭了。

FJ命令奶牛i应该从i号隔间开始收集糖果。如果一只奶牛回到某一个她已经去过的隔间，她就会停止收集糖果。

在被迫停止收集糖果之前，计算一下每头奶牛要前往的隔间数（包含起点）。

输入格式

第1行 整数n。

第2行到n+1行 每行包含一个整数 next_i 。

输出格式

n行，第i行包含一个整数，表示第i只奶牛要前往的隔间数。

输入输出样例

#include<bits/stdc++.h>
using namespace std;
#define maxn 100010

int n;
int f[maxn],p[maxn];
int ans=0;


int find(int x){
	ans++;//记录环长度 
	if(x==f[x]) return x;
	else return find(f[x]);
}
int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	
	
	cin>>n;
	int i,j,t,s;
	for(i=1;i<=n;i++) f[i]=i,p[i]=maxn;//f[i] 路径初始化   p[i] 路径长路初始化 
	
	for(i=1;i<=n;i++){
		ans=0;
		cin>>t;
		s=find(t);
		if(s==i){//找到环，环内每个牛走的路径长为环长 
			for(j=t;;j=f[j]) {p[j]=ans;if(j==i)break;}
		}
		else f[i]=t;
	}
	
	for(i=1;i<=n;i++){
		if(p[i]!=maxn)
		    cout<<p[i]<<endl;
		else {
			ans=0;
			int a=f[i];
	        while(1){
	    	    ans++;
	    	    if(p[a]!=maxn){
	    	    	p[i]=p[a]+ans;
	    	    	cout<<p[i]<<endl;
	    	    	break;
				}
			    a=f[a];
		    }
		}
	}
	return 0;
}