C++(g++ 7.5.0) 解法, 执行用时: 72ms, 内存消耗: 1204K, 提交时间: 2023-04-17 17:20:33

#include<bits/stdc++.h>
#define N 10000005
using namespace std;
int fa[N],n,m,p,cnt,ans=0x3f3f3f3f;
int find(int x,int &cnt){
	cnt++;
	if(x==fa[x]){
		return x;
	}
	return find(fa[x],cnt);
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		cnt=0;
		if(find(x,cnt)==i){
			ans=min(ans,cnt);
		}
		else{
			fa[i]=x;
		}
	}
	cout<<ans<<endl;
}

C++14(g++5.4) 解法, 执行用时: 60ms, 内存消耗: 1912K, 提交时间: 2020-10-08 18:08:21

#include<bits/stdc++.h>
using namespace std;
int n,i=1,f[200001],a[200001],x,m=2e9;
int fd(int x)
{
	if(x!=f[x])
	{
        int t=f[x];
		f[x]=fd(f[x]);
        a[x]+=a[t];
	}return f[x];
}main()
{
	cin>>n;
	for(;i<=n;i++)f[i]=i;
	for(i=1;i<=n;i++)
	{
		cin>>x;
		if(fd(x)!=fd(i))
		{
			a[i]=a[x]+1;
			f[fd(i)]=fd(x);
		}else m=min(m,a[x]+a[i]+1);
	}cout<<m;
}

C++(clang++ 11.0.1) 解法, 执行用时: 83ms, 内存消耗: 1968K, 提交时间: 2022-11-25 14:11:31

#include<bits/stdc++.h>
using namespace std;
int n,i=1,f[200001],a[200001],x,m=2e9;
int fd(int x){
	if(x!=f[x]){
        int t=f[x];
		f[x]=fd(f[x]),a[x]+=a[t];
	}return f[x];
}
int main(){
	cin>>n;
	for(;i<=n;i++)f[i]=i;
	for(i=1;i<=n;i++){
		cin>>x;
		if(fd(x)!=fd(i)){
			a[i]=a[x]+1;
			f[fd(i)]=fd(x);
		}else m=min(m,a[x]+a[i]+1);
	}cout<<m;
}