DSU(Disjoint Set Union) / Union Find

Disjoint Set Union Disjoint Set(서로소 집합)이란 서로 공통된 원소가 없는 집합을 말합니다. 보통 Union Find 라고 불립니다. Union 2개의 집합을 1개의 집합으로 합치는 방식입니다. 기본적으로 높이 가 작은 쪽을 큰 쪽으로 합칩니다. 유니온 바이 랭크(Union by rank) 두개의 disjoint set 을 합칠 때 항상 작은 쪽을 큰 쪽에 합칩니다. Find 어떤 element가 주어질때, 이 element 가 속해져 있는 루트 를 반환합니다. 아래 예시에서는 3 이라는 원소를 Find 하게 되면 루트인 6이 나오게 됩니다. 경로 압축 경로 압축은 Find 의 시간 복잡도를 개선하기 위해 원소를 Find 할 경우 바로 루트원소가 나올 수 있도록 하는 방법입니다...