Submission #423326

---

Source Code Expand

#include<iostream>
#include <vector>

namespace graph{
	using namespace std;

	class UnionFind{
	public:
		//nは要素数
		UnionFind(int n) :
			par(n),
			rank(n)
		{
			for (int i = 0; i < n; ++i){
				par[i] = i;
			}
		}

		//xとyの属する集合を結合
		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);
		}



	private:
		//親
		vector<int> par;

		//根の深さ
		vector<int> rank;

		//木の根を求める
		int find(int x){
			if (par[x] == x){
				return x;
			}
			else{
				return par[x] = find(par[x]);
			}
		}
	};
}

using namespace std;
int main(){
	int N,Q;
	cin >> N>>Q;
	graph::UnionFind uni(N);
	for (int i = 0; i < Q; i++){
		int p, x, y;
		cin >> p >> x >> y;
		if (p){
			if (uni.same(x, y))
				cout << "Yes" << endl;
			else
				cout << "No" << endl;
		}
		else 
			uni.unite(x, y);
	}
	return 0;
}

Submission Info

Judge Result