Submission #4038699

---

Source Code Expand

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

int n;
int parent[100004], size[100004], r[100004],p[100004],m,x,y;

void init(){
	for(int i = 1;i<=n;i++){	
		parent[i] = i; 
		size[i] = 1; 
		r[i] = 0;
	}
}
int find(int p){
	if(parent[p] == p)	return p;
	else return parent[p] = find(parent[p]);
}
void uni(int p, int q){
	p = find(p);
	q = find(q);
	if(r[p]<r[q]) parent[p] = q, size[q] += size[p];
	else	parent[q] = p, size[p] += size[q];
	if(r[p] == r[q])	r[p]++;
}

int main() {
	cin>>n>>m;
	for(int i = 1; i <= n; i++)	cin>>p[i];
	init();
	while(m--){
		cin>>x>>y;
		if(find(x)==find(y))	continue;
		uni(x,y);
	}
	int cnt = 0;
	for(int i = 1;i<=n;i++){
		if(p[i] == i){
			cnt++;
			continue;
		}
		if(find(p[i]) == find(i))	cnt++;
	}
	cout<<cnt;
	return 0;
}

Submission Info

Judge Result