집합의 표현(Union-Find)

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

1717번: 집합의 표현

 

분리 집합(Disjoint Set): 교집합이 존재하지 않는 두 개 이상의 집합. 구분해야 하는 데이터 집합을 다룰때 사용함.

 

분리 집합은 보통 Union-Find 알고리즘을 사용하여 트리 구조로 구현한다.

 

Union-Find 알고리즘

1. make_set(x) -> x원소를 유일하게 갖고있는 집합을 생성.

2. union(x, y) -> x가 속한 집합과 y가 속한 집합을 합친다.

3. find(x) -> x가 속한 집합을 찾는다.

 

Union-Find 알고리즘(Tree)

1. make_set(x) -> 각 원소를 전부 루트노드로 만든다. 루트노드 = 자기자신.

2. union(x, y) -> x가 속한 트리와 y가 속한 트리의 루트노드를 찾는다(find). 루트 노드가 다르다면 x를 y의 부모노드로 만들어서 트리를 합친다.

3. find(x) -> x가 속한 트리의 루트노드를 찾는다.

 

집합의 표현 문제는 숫자의 범위가 '0~1000000'으로 주어졌다. 단순히 Union-Find 알고리즘을 사용하여 트리를 구성하게 된다면 최악의 경우에 find마다 O(N-1)의 시간 복잡도가 발생할 수 있어서 시간초과가 발생한다.

find 함수에서 재귀함수 호출을 통한 트리의 모든 노드의 부모노드를 루트노드로 만들어주어서 경로의 압축을 구현해주어야 한다.

 

#include <iostream>
using namespace std;

int parent[1000001];

int find_parent(int index)
{
	// 재귀호출을 통한 부모노드 = 루트노드화로 경로압축
	if (parent[index] == index) return index;
	else parent[index] = find_parent(parent[index]);
	return parent[index];
}

int main()
{
	ios::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;
	}

	while (m--)
	{
		int cmd, n1, n2;
		cin >> cmd >> n1 >> n2;
		if (n1 > n2)
		{
			int tmp = n1;
			n1 = n2;
			n2 = tmp;
		}
		int pn1 = find_parent(n1);
		int pn2 = find_parent(n2);
		switch (cmd)
		{
		case 0:
			if (pn1 != pn2) parent[pn2] = pn1;
			break;
		case 1:
			if (pn1 == pn2) cout << "YES";
			else cout << "NO";
			cout << '\n';
			break;
		default:
			break;
		}
	}
}