BOJ 1717 | 집합의 표현

간단한 Union Find 구현 문제다.

Union Find 알고리즘은 Disjoint set 을 나타내는 알고리즘인데, 간단히 말하면 겹치는 부분이 없는 집합을 말한다.

$\{1, 2\}, \{3\}, \{4\}$ 처럼 부분집합들 사이에 겹치는 부분이 없는 것을 서로소 집합이라고 하고, 이 상태를 유지하면서 하는 연산을 처리하는 알고리즘이 Union Find이다.

보통은 트리 구조로 구현한다.

tree[i] 가 i의 부모 노드를 나타내도록 구현하면 된다.

C++의 class를 이용해서 조금 깔끔하게 만들어 봤다.

코드

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

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define FASTIO ios_base::sync_with_stdio;cin.tie(nullptr);cout.tie(nullptr);

#define debug if constexpr (local) std::cout
#define endl '\n'

class UnionFind{
private:
	vector<int> parent;
public:
	UnionFind(int n){
		parent.resize(n+1);
		for (int i = 0; i <= n; i++){ // parent[i] = i's parent
			parent[i] = i;
		}
	}
	int Find(int x){
		if (x == parent[x]) return x;
		return parent[x] = Find(parent[x]);
	}
	void Union(int x, int y){
		x = Find(x);
		y = Find(y);
		parent[y] = x;
	}
	vector<int> tree(){
		return parent;
	}
};

int main(){
	FASTIO;
	
	int N, M; cin >> N >> M;
	UnionFind S = UnionFind(N);
	
	for (int i = 0; i < M; i++){
		int c, x, y; cin >> c >> x >> y;
		if (c == 0){
			S.Union(x, y);
		}
		else{
			if ( S.Find(x) == S.Find(y) ) cout << "yes" << endl;
			else cout << "no" << endl;
		}
	}
	
}