개발조아

문제 링크 : https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net MST 문제이다. 나는 크루스칼로 풀이 했다. 문제는 마을을 두개로 분리하고 두부분의 가중치의 합이 최소가 되어야한다. 정점을 n이라 했을 때 n-2개의 간선은 고르면 된다. MST 문제를 풀때 n-1개의 간선을 고르면 된다. n-1개를 고르면 하나의 그래프가 탄생하고 사이클이 형성되지 않은 상태이다. 이때 간선을 하나 지우면 두개의 그래프가 나..