[BOJ] 8872번: 빌라봉

https://www.acmicpc.net/problem/8872

connected component 각각을 하나의 vertex로 보고, 여기서 N-M-1개의 edge를 추가해 tree를 만든다고 해봅시다. tree를 뭐 어찌저찌 만들어놓고 가장 오래 걸릴 경로를 생각해보면 각 connected component에서 연결된 edge가 부착된 점까지의 거리가 가장 긴 점이고, 이는 곧 해당 connected component에서의 반지름을 최대한 작게 만들어야 하는 문제로 치환할 수 있습니다.

그리고 connected component간의 연결은 가장 반지름이 긴 connected component에서 불가사리 형식으로 된 것이 가장 효율적임을 알 수 있습니다.

https://github.com/blisstoner/BOJ/blob/master/8872.cpp