[Algorithm/C++] Union & Find

Union & Find

Disjoint Set을 표현할 때 사용하는 알고리즘

※ Disjoint Set이란?
서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조
= "서로소 집합 자료구조"

---

연산

1. make-set(x) 초기화
   : x를 유일한 원소로 하는 새로운 집합을 만든다.
2. union(x, y) 합하기
   : x가 속한 집합과 y가 속한 집합을 합친다.
3. find(x, y) 찾기
   : x가 속한 집합의 대표값(루트 노드 값)을 반환한다. 즉, x가 어떤 집합에 속해 있는지 찾는 연산

과정

[출처] https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html

구현

int find(int x) {	// 최상단 노드 찾기
	if (parent[x] == x) return x;
	else return parent[x] = find(parent[x]);
}

void Union(int a, int b) {	// find 함수 이용해 경로 압축
	parent[find(a)] = find(b);
}