[알고리즘] 서로소 집합(Disjoint-sets)

상호배타 집합: 서로 중복하게 포함된 원소가 없는 집합들을 뜻한다.

집합에 특정한 멤버를 대표자라고 하며 각 집합을 구분한다.

상호배타집합 표현방법
=> 연결리스트,  트리

연결리스트 
1.같은 집합의 원소들은 하나의 연결리스트로 관리
2.맨 앞의 원소가 대표원소
3. 각 원소는 대표를 가리키는 링크를 갖음

트리 
1. 하나의 잡합을 하나의 트리
2. 자식노드는 부모노드를 가리킨다. 따라서 가장 상위에 있는 루트 노드가 대표자가 된다.

연산
Make-Set(x) :멤버x만 포함하는 새로운 집합을 생성
Find-Set(x) :원소 x가 속한 집합을 알아내기 위함, 대표자를 알아내기 위함
Union(x,y) : x가 속한 집합과 y가 속한 집합을 하나의 집합으로 합침

연산의 효율을 높이는 방법
1.  union에서 rank를 이용함
각 노드는 자신을 루트로 하는 트리의 높이를 rank로 저장한 뒤 두 집합을 합칠 때 랭크가 낮은 집합을 높은 집합에 붙인다.
2. path compression
 Fine-set하는 과정에서 모든 노드들이 루트를 가리키도록 변경시켜준다.