MST 구현 품질
입력 형태를 보고 알고리즘을 고른 뒤, 같은 검증식을 적용한다
Kruskal과 Prim은 접근이 달라도 최종 검증은 같습니다. 사이클 없음, 전체 연결, V-1개 채택을 확인하세요.
Kruskal edge first
입력이 간선 목록이면 정렬 후 DSU로 사이클을 제외합니다. 로그는 `edge, rootU, rootV, take`가 중심입니다.
Prim vertex first
입력이 인접 리스트이고 시작 정점에서 확장하기 좋으면 힙으로 가장 싼 외부 간선을 고릅니다.
연결 그래프?비연결이면 MST가 아니라 forest입니다.
사이클 제외?같은 컴포넌트 간선은 비용이 작아도 제외합니다.
채택 수 V-1?정점 V개를 잇는 간선 수는 정확히 V-1개입니다.
동점 안정?간선 순서는 달라도 총 비용은 같아야 합니다.
sorted weight
find(u), find(v)
take / skip
used count
total cost