MST + DSU

싼 간선을 고르되, 사이클이면 버린다

Kruskal은 비용순으로 후보를 보지만, 채택 기준은 두 정점의 대표가 다른가입니다.

1. Sort간선을 비용 오름차순 정렬
2. Find양 끝 정점의 DSU 대표 확인
3. Union대표가 다르면 채택하고 병합
4. Stop채택 간선이 V-1개면 완성

작은 예제: 1-3은 싸 보여도 마지막에는 사이클

1 2 3 1 2 3
1-2 (1)채택
2-3 (2)채택
1-3 (3)제외

5초 판단 규칙

find(u) != find(v) 서로 다른 컴포넌트를 잇는다. 간선을 MST에 넣고 union한다.
find(u) == find(v) 이미 이어져 있다. 추가하면 사이클이므로 비용이 작아도 버린다.
핵심: MST는 “최소 비용 간선 목록”이 아니라 사이클 없는 V-1개 연결이다.