[백준][1717] 집합의 표현

이 포스트는 백준 사이트의 집합의 표현 문제 풀이입니다.

문제

해결 과정

이 문제는 Union-Find 알고리즘을 활용하면 쉽게 해결할 수 있습니다.

첫 상태는 문제의 설명처럼 0부터 N까지의 각 숫자가 독립적으로 존재하는 상태에서
사용자의 합집합 연산과 집합 확인 연산을 반복적으로 수행하면 됩니다.

여기서 합집합 연산에 사용되는 것이 Union 연산이고
사용자가 입력한 두 숫자의 관계를 확인하기 위해 사용하는 것이 Find 연산입니다.

코드 구현

#include <iostream>
#include <vector>

vector<int> group;
void Merge(int x, int y);
int Find(int x);

int main() {
	int N, M;
	cin.tie(0)->sync_with_stdio(false);
	cin >> N >> M;
	
	for (int i = 0; i <= N; ++i) {
		group.push_back(i);
    }
	
	for (int i = 0; i < M; ++i) {
		int q, a, b;
		cin >> q >> a >> b;

		if (q == 1) {
			if (Find(a) == Find(b)) printf("YES\n");
			else printf("NO\n");
		}
		else {
			Merge(a, b);
		}
	}

	return 0;
}


void Merge(int x, int y) {
	x = Find(x);
	y = Find(y);

	if (x == y) return;
	group[x] = y;
}

int Find(int x) {
	if (group[x] == x) return x;
	else return group[x] = Find(group[x]);
}

실행 결과