ARC073 B問題

D - Equals

与えられるデータセットにて、どことどこが交換できるかについて教えてもらえる。
その交換できる木の中で目的の場所まで移動できればOK
木の作り方は幅優先探索を選択


#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <queue>

using namespace std;

int main(){

	int n,m;
	vector<int> p;
	map<int,vector<int>> xy;
	char flag[100010];

	for(int i=0;i<100010;i++){
		flag[i]=0;
	}

	cin>>n>>m;
	for(int i=0;i<n;i++){
		int tmp;
		cin>>tmp;
		p.push_back(tmp-1);
	}
	for(int i=0;i<m;i++){
		int tmpX,tmpY;
		cin>>tmpX>>tmpY;
		xy[tmpX-1].push_back(tmpY-1);
		xy[tmpY-1].push_back(tmpX-1);
	}

	/*学習実施、どことどこが繋がってるのか?*/
	
	int ans=0;
	for(int i=0;i<n;i++){
		if(flag[i]==1)continue;
		queue<int> q;
		q.push(i);
		set<int> touch;
		touch.insert(i);
		flag[i]=1;
		while(q.size()!=0){
			int now = q.front();
			q.pop();
			if(xy[now].size()==0)continue;
			int size = xy[now].size();
			for(int j=0;j<size;j++){
				int next = xy[now].at(j);
				if(flag[next]==0){
					touch.insert(next);
					flag[next]=1;
					q.push(next);
				}
			}
		}
		for(auto itr = touch.begin(); itr != touch.end();itr++){
			int targetPos = p[*itr];
			if(touch.count(targetPos)==1){
				ans++;
			}
		}
	}
	cout<<ans<<endl;
	return 0;

}