[자료구조론] Disjoint Set(서로소 집합)

Disjoint Set 서로소 집합이란 공통원소가 없는 두 집합을 뜻합니다. disjoint set 알고리즘은 이 개념을 사용하는 알고리즘입니다. disjoint set의 기본 연산은 union과 find로 이루어집니다. Union-Find in disjoint sets S의 elements는 inverted tree로 표현됩니다. 다시 말해, 이 알고리즘에서 tree의 포인터는 위쪽을 향한다는 뜻입니다. 따라서 tree의 root는 NULL parent pointer를 가지게 됩니다. 또한 두 element가 같은 집합에 있다면 이는 곧 그들이 같은 tree에 있다는 뜻입니다. 반대의 경우 역시 성립합니다. 집합은 순서를 상관쓰지 않으므로 만들어지는 tree는 unique하지 않습니다. tree가 어떻..