蓝名菜鸡求助小黄题
查看原帖
蓝名菜鸡求助小黄题
443642
一只小可爱吖楼主2021/3/8 19:18

RT,10分,看了一下第一篇题解,还是看不出哪里错了

#include<bits/stdc++.h>
using namespace std;
int n,dis[200002],f[200002],ans=1e9;
int zqq(int k){
	if(f[k]==k)return k;
	dis[k]+=dis[f[k]];
	return f[k]=zqq(f[k]);
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		f[i]=i;
	for(int i=1;i<=n;i++){
		int to;
		cin>>to;
		int x=zqq(i),y=zqq(to);
		if(x!=y){
			f[x]=y;
			dis[i]=dis[to]+1;
		}
		else
			ans=min(ans,dis[i]+dis[to]+1);
	}
	cout<<ans;
	return 0;
}
2021/3/8 19:18
加载中...