[백준][C++] 1647 도시 분할 계획

1647. 도시 분할 계획 문제 풀이 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 문제가 길지만... 해석해보면 하나의 최소 신장 트리를 두 개로 나눴을 때, 최소 간선의 수를 구하는 것이다. 사실 처음에는 조금 어렵다고 느꼈지만... 시각적으로 최소 스패닝 트리를 보니 어떻게 구현해야할지 바로 알 수 있었다! 이 트리를 보니, 확실히 알았다. 이 트리에서 두 개의 최소 신장 트리로 분할하려면 어떻게 해야할까? 일단, 간선 하나를 제거해야할 것이다. 그래야 두 개로 나..

원문링크 : [백준][C++] 1647 도시 분할 계획