MST + Union-Find 요약
MST는 “싸고 안전한” 간선만 V-1개 고르는 문제다
전체 구현은 네 단계로 기억하면 됩니다. 정렬은 후보 순서를 만들고, DSU는 사이클을 막으며, 채택 수가 연결성을 증명합니다.
1. 후보 정렬간선 비용 오름차순으로 본다.
2. 대표 확인find(u), find(v)로 컴포넌트를 비교한다.
3. 안전 간선 채택대표가 다를 때만 MST와 DSU에 반영한다.
4. 연결성 확인채택 간선 수가 V-1인지 마지막에 본다.
반드시 기억할 3문장
1최소 비용은 “정렬 순서”이고, 정답 조건은 “사이클 없는 연결”이다.
2같은 대표를 잇는 간선은 이미 연결된 두 정점을 다시 잇는다.
3모든 정점을 잇지 못하면 총 비용이 있어도 MST가 아니다.
최종 판정
find(u) != find(v)
채택, union, used++, total += w
find(u) == find(v)
사이클이므로 skip, DSU와 비용은 그대로
실전 체크: 정렬 비용 `O(E log E)`, DSU 비용은 거의 상수,
마지막 답은 `used == V - 1`일 때만 유효합니다.