집합의 표현 (feat. 백준, 1717번)

집합의 표현
https://www.acmicpc.net/problem/1717

1717번: 집합의 표현

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <vector>
using namespace std;
int N, M;
int arr[1000001];
int find(register int num) {
	if (arr[num] < 0)
		return num;
	return arr[num] = find(arr[num]);
}
void merge(register int a, register int b) {
	a = find(a);
	b = find(b);
	if (a != b)
		arr[a] = b;
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	cin >> N >> M;
	for (register int n = 0; n <= N; ++n)
		arr[n] = -1;
	for (register int m = 0, q, a, b; m < M; ++m) {
		cin >> q >> a >> b;
		if (q == 0) {
			merge(a, b);
		}
		else {
			if (find(a) == find(b))
				cout << "YES" << "\n";
			else
				cout << "NO" << "\n";
		}
	}
	return 0;
}
// *&)*@*