Union-Find

disjoint-set 이라고도 불리는 자료구조이며,

주 용도는 undirected graph 에서 두 vertex가 연결되어 있는지를 체크하고, 새로운 두 그룹을 union 할 수 있다.

아래의 코드는 path compression과 size비교를 통해 더 큰 tree를 부모로 삼는 방법이 적용된 것이다.

이 때, union, find 두 연산 모두 시간복잡도는 O(log*V)이며 거의 상수시간에 가깝다.

이 자료구조를 통해서 대표적으로 kruskal algorithm을 이용할 때 써먹으니 기억 해 두자.