Union-Find 란? Disjoint Set을 표현할 때 사용하는 알고리즘 그렇다면 Disjoint Set(서로소 집합, 상호 배타 집합) 이란 ? 서로 공통된 원소를 가지고 있지 않은 두 개 이상의 집합을 말한다. 집합에 속한 하나의 특정 멤버(root node)를 통해 각 집합들을 구분한다. 이를 대표자(representative)라 한다. 상호 배타 집합을 표현하는 방법 트리 하나의 집합을 하나의 트리로 표현 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 된다. 연결 리스트보다 효율적이다. 연결 리스트 같은 집합의 원소들은 하나의 연결 리스트로 관리 연결 리스트의 맨 앞의 원소를 집합의 대표 원소로 삼는다. 각 원소는 집합의 대표 원소를 가리키는 링크를 갖는다. 상호 배타 집합 연산 m..