서로소 집합(Disjoint-set)

서로소 집합

서로소 집합(상호베타 집합)이란?
중복되는 원소가 없는 집합
교집합이 공집합인 집합

집합은 어떻게 구분할까?

-> 집합에 속한 특정 멤버(대표자)를 통해 집합을 구분

서로소 집합 표현 방법

1. 연결리스트
   - 연결리스트 맨 앞 원소를 대표 원소로 잡기
   - 각 원소는 대표원소 가리키는 링크 가지고 있다
2. 트리
   - 자식노드가 부모노드를 가리키며, 루트노드가 대표자

서로소 집합 연산

1. Make-Set(x) : 유일한 멤버 x를 포함한 집합을 생성

Make-Set(x):
	p[x] <- x

2. Find-Set(x) : x가 어디 집합에 포함되어 있는지 찾기 -> 대표자를 리턴

Find-Set(x):
	if x == p[x] : return x
        else         : return Find_Set(p[x])

3. Union(x,y) : x가 포함된 집합과 y가 포함된 집합 합치기

Union(x,y):
	if Find-Set(y) == Find-Set(x) return;
        p[Find-Set(y)] <- Find-Set(x)

연산의 효율 높이기

1. Rank를 이용한 Union
   각 노드는 자신을 루트로 하는 subtree 높이를 Rank로 저장한다
   두 집합을 합칠 때 rank 높은집합에 붙이기
2. Path compression
   Find-Set 할때 모든 노드들의 포인터를 root로 변경해주기

Find-Set(x):
	if x == p[x] : return x
        else         : return p[x] = Find_Set(p[x])