[BOJ] 1717 집합의 표현 C++

개요

https://www.acmicpc.net/problem/1717

1717번: 집합의 표현

골드4 난이도 문제다.

풀이

유니온 파인드 그 자체인 문제다.

유니온 파인드에 필요한 Initialize, FInd, Union 기능을 구현하면 된다.

Find 함수에서 경로 압축 최적화를 통해 연산 시간을 줄였다.(Path Compression)

Union 함수에서는 레벨이 낮은 트리가 높은 트리에 들어갈 수 있도록 최적화 했다.(Union-by-rank)

코드

#include<iostream>
#include<algorithm>
using namespace std;
constexpr int LIMIT = 1000002;

int parent[LIMIT];
int level[LIMIT];

void Init(int n)
{
	for (int i = 0; i <= n; i++)
	{
		parent[i] = i;
		level[i] = 1;
	}
}
int Find(int n)
{
	if (parent[n] == n) return n;

	return parent[n] = Find(parent[n]);
}
void Union(int a, int b)
{
	a = Find(a);
	b = Find(b);

	if (level[a] > level[b])
		swap(a, b);
	else if (level[a] == level[b])
		level[b]++;

	parent[a] = b;
}

int main()
{
	cin.tie(0)->sync_with_stdio(0);

	int n, m;
	int cmd, a, b;
	string ans;

	cin >> n >> m;
	Init(n);

	for (int i = 0; i < m; i++)
	{
		cin >> cmd >> a >> b;
		if (cmd == 0) Union(a, b);
		else {
			ans = (Find(a) == Find(b)) ? "YES\n" : "NO\n";
			cout << ans;
		}
	}
}