Kruskal MST
정렬된 간선을 DSU 필터에 통과시킨다
간선은 비용순으로 보지만, MST에 들어가는지는 사이클을 만들지 않는지가 결정합니다.
가중치 오름차순 처리 로그
1-2 / 1
대표가 다름: 두 컴포넌트 연결
accept
2-3 / 2
대표가 다름: 3번 정점 편입
accept
1-3 / 3
대표가 같음: 사이클 발생
skip
3-4 / 4
대표가 다름: 마지막 정점 연결
accept
완성 조건
4정점 수 V
3채택 간선 V-1
7총 비용
1-2
2-3
3-4
연결성 검증: 모든 간선을 봤는데 채택 수가 V-1보다 작으면
MST가 아니라 forest입니다. 이때는 `-1` 또는 불가능 처리가 필요합니다.
sort(edges by weight)
for (u, v, w) in edges:
if find(u) != find(v): take edge, union, used++
answer is valid only when used == V - 1
for (u, v, w) in edges:
if find(u) != find(v): take edge, union, used++
answer is valid only when used == V - 1