MST 검증 조건

MST는 간선 채택과 DSU 병합을 분리해서 본다

Kruskal 구현은 정렬된 간선, find 결과, 채택 간선 수를 나눠 검증해야 비연결 그래프를 놓치지 않습니다.

간선 정렬

비용 기준을 먼저 확정

가중치 오름차순과 동점 처리 규칙을 먼저 고정합니다.

루트 비교

대표가 다를 때만 채택

두 끝점의 대표가 다를 때만 간선을 채택하고 union을 수행합니다.

채택 개수

완성 조건을 수로 확인

정점 수가 V라면 MST는 V-1개 간선을 가져야 완성됩니다.

사이클 차단
사이클 차단 같은 대표를 가진 간선은 비용이 작아도 버립니다.
압축 검증 경로 압축과 rank/size 갱신이 parent 배열을 깨지 않는지 봅니다.
비연결 처리 끝까지 V-1개를 못 고르면 MST가 아니라 forest 결과로 해석합니다.