백준 1717번 : 집합의 표현

문제 링크 : www.acmicpc.net/problem/1717

내 풀이(2021.2.4.) : 유니언 파인드

#include <iostream>

using namespace std;

int parent[1000001];

int find(int x) {
	if (parent[x] != x) parent[x] = find(parent[x]);
	return parent[x];
}

void union_(int a, int b) {
	a = find(a); b = find(b);
	if (a < b) parent[b] = a;
	else parent[a] = b;
}

void same(int a, int b) {
	if (find(a) == find(b)) cout << "YES" << '\n';
	else cout << "NO" << '\n';
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m; cin >> n >> m;

	for (int i = 0; i <= n; i++) {
		parent[i] = i;
	}

	for (int i = 0; i < m; i++) {
		int k, a, b; cin >> k >> a >> b;
		if (k == 0) {
			union_(a, b);
		}
		else {
			same(a, b);
		}
	}

	return 0;
}

- parent의 초기화 주의 (이 문제의 범위 조건 상 n도 초기화 해야 함)

- 같은 집합인지 비교할 때, parent를 비교할 것이 아니라 find를 통해 비교해야 함