Submission #4029374

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int n,m;
int p[111111];
int x[111111],y[111111];
int par[111111];
int Rank[111111];
void init(int n){
	for(int i=0;i<n;i++){
		par[i]=i;
		Rank[i]=0;
	}
}
int find(int x){
	if(par[x]==x)return x;
	return par[x]=find(par[x]);
}
void unite(int x,int y){
	x=find(x);y=find(y);
	if(x==y)return;
	if(Rank[x]<Rank[y])par[x]=y;
	else{
		par[y]=x;
		if(Rank[x]==Rank[y])Rank[x]++;
	}
}
bool same(int x,int y){
	return find(x)==find(y);
}
signed main(){
	cin>>n>>m;
	rep(i,n)cin>>p[i];
	init(n);
	rep(i,m){
		cin>>x[i]>>y[i];
		unite(x[i]-1,y[i]-1);
	}
	int ans=0;
	rep(i,n){
		if(same(p[i]-1,i))ans++;
	}
	cout<<ans<<endl;
	return 0;
}

Submission Info

Judge Result