DSU 기본 구현
find는 대표를 찾고, union은 다른 집합만 합친다
MST에서 DSU는 간선 추가 전 사이클을 판정하는 도구입니다. 대표가 같으면 추가하지 않는 것이 핵심입니다.
현재 parent 배열
1parent[1]
1parent[2]
1parent[3]
4parent[4]
1
2
3
4
입력 연산의 판정
union(1, 2)
대표가 다름: 1번 집합과 2번 집합 병합
true
union(2, 3)
find(2)가 1로 압축되고 3을 같은 집합으로 병합
true
union(1, 3)
둘 다 대표가 1: MST 간선이면 사이클
false
find(x)대표까지 올라가며 parent를 바로 대표로 고친다.
union(a,b)대표가 다를 때만 size/rank 기준으로 붙인다.
MST 판정false가 나온 간선은 비용이 작아도 채택하지 않는다.