[C++] 백준 1717번 - 집합의 표현

Disjoint - Set 문제. 이를 분리 집합이라고도 하는데 Disjoint-Set이 더 어울리는 것 같다.

이 문제는 O(n)에 풀면 안되는 문제이다.

Disjoint-Set의 find는 항상 최고의 조상을 찾아야하기 때문에 시간을 줄이는 곳에서 애를 먹었다.

이 방식을 Path Compression 방법으로 사용하면 AC를 받을 수 있다. 

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

int n, m;
int p[1000005];
int op, a, b;

int find(int x) {
	if (x == p[x])
		return x;
	else 
		return p[x] = find(p[x]);
}

void unite(int x, int y) {
	x = find(x);
	y = find(y);
	if (x < y) p[y] = x;	
	else if (x > y) p[x] = y;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> m;
	for (int i = 0; i <= n; i++) p[i] = i;
	
	while(m--) {
		cin >> op >> a >> b;
		if (op == 0) unite(a, b);
		else  {
			if (find(a) == find(b)) cout << "YES" << endl;
			else cout << "NO" << endl;
		}
	}
	return 0;
}