알고리즘 8장
MST/DSU: DSU 기본 구현
DSU는 find와 union으로 서로소 집합을 관리하며, 경로 압축과 rank/size 기준 병합으로 거의 상수 시간에 가깝게 동작합니다.
상태 변화
집합 병합
1
parent 1
2
parent 1
3
parent 3
4
parent 3
find(2)
→
root 1
→
compress
불변식
점검
find(x)
x가 속한 집합의 대표자를 찾습니다.
path compression
find 과정에서 중간 노드 parent를 대표자로 줄입니다.
union(a,b)
두 대표자가 다를 때 한 집합으로 병합합니다.
rank/size
작은 트리를 큰 트리 아래에 붙여 높이 증가를 줄입니다.