[BOJ]1647번: 도시 분할 계획

문제: https://www.acmicpc.net/problem/1647

---

Union-find 문제입니다.

 

모든 도시가 연결되어 있다는 가정이 있으므로 그래프 => 트리로 만들 수 있습니다.

그리고 모든 도시를 연결하는 트리의 최소 비용은 MST로 만들 수 있습니다.

 

MST를 구성한 상태에서 하나의 간선만 제외하면 도시(컴포넌트)를 2개로 나눌 수 있습니다.

제외하는 한 개의 간선은 MST 간선 중 최대 비용 간선입니다.

---

코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ1647.java