MST와 유니온 파인드

간선을 정렬한다

가장 싼 간선부터 보되 이미 같은 컴포넌트를 잇는 간선은 사이클을 만들므로 버린다.

find에서 경로 압축을 적용하면 이후 대표 조회 비용이 거의 상수에 가까워진다.

선택한 간선 수가 n-1보다 작으면 그래프가 연결되지 않았다는 뜻이다.

Kruskal

간선 중심 간선 수가 적고 정렬 비용을 감당할 수 있을 때 단순하다.

Union-Find와 짝이다.

Prim

정점 확장 현재 트리에서 가장 싼 바깥 간선을 우선순위 큐로 고른다.

밀집 그래프에서 후보가 된다.

Path compression

find 최적화 대표를 찾는 경로의 부모를 바로 대표로 바꾼다.

rank/size union과 함께 쓴다.

Disconnected

MST 없음 모든 정점을 연결하지 못하면 최소 신장 숲만 만들어진다.

문제 출력 규칙을 확인한다.

정렬 간선이 비용 오름차순으로 처리되는가.

사이클 같은 대표를 가진 두 정점을 잇는 간선을 건너뛰는가.

연결 선택된 간선 수가 n-1인지 확인하는가.

sort(edges.begin(), edges.end());
for (auto [w, a, b] : edges) {
    if (find(a) == find(b)) continue;
    unite(a, b); total += w; ++picked;
}