[알고리즘] Union-Find 알고리즘 - Heee's Development Blog
서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다.
Disjoint-Set을 표현할 때 사용하는 알고리즘 이다. 배열로 구현할 수 있지만 시간복잡도의 이점때문에 트리를 이용해서 구현한다.
같은 집합을 하나의 '트리'라고 둔다. 이때 트리의 루트 노드가 집합의 번호가 된다.
x를 유일한 원소로 하는 새로운 집합을 만든다.
x가 속한 집합과 y가 속한 집합을 합친다. 즉, x와 y가 속한 두 집합을 합치는 연산이다.
x가 속한 집합의 대푯값(루트 노드의 값)을 반환한다. 즉, x가 어떤 집합에 속해 있는지 찾는 연산이다.
disjoint-set을 트리로 표현한다. 노드$i$가 속해있는 집합(트리)의 루트 노드를 $\text{root}[i]$라고 하자.