Submission #423631

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
class UnionFind {
	vector<int> par,rank;
	public:
	UnionFind(int n){
		for(int i=0;i<n;i++){
			par.push_back(i);
			rank.push_back(0);
		}
	}
	int find(int x){
		if(par[x]==x)
			return x;
		else
			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);
	}
};

int main () {
	int n,q;
	cin >> n >> q;
	UnionFind uf(n);
	for(int i=0;i<q;i++){
		int p,a,b;
		cin >> p >> a >> b;
		if(p==0){
			if(uf.same(a,b)==false){
				uf.unite(a,b);
			}
		}else{
			if(uf.same(a,b))
				cout<<"Yes"<<endl;
			else
				cout<<"No"<<endl;
		}
	}
	return 0;
}

Submission Info

Judge Result