MST/DSU 점검

MST는 채택 간선 수로 연결성 검증

Kruskal과 Prim은 최소 비용을 구하지만, 실제 구현 검증은 간선 정렬, 사이클 제외, 채택 간선 수 확인을 나눠 보는 것이 안전합니다.

01

간선 정렬

가중치 기준 정렬인지 튜플 순서를 혼동하지 않았는지 확인합니다.

02

사이클 제외

DSU find 결과가 같은 간선은 채택하지 않아 트리 구조를 유지합니다.

03

연결성 판정

채택 간선 수가 V-1보다 작으면 MST가 아니라 최소 신장 숲입니다.

1

model

무방향 그래프 전제가 맞는지 확인합니다.

2

sort

간선 튜플의 가중치 위치를 점검합니다.

3

dsu

경로 압축과 union 기준을 적용합니다.

4

count

채택 간선 수와 총 비용을 함께 검증합니다.