최소 스패닝 트리를 이용해서 그래프를 두 집합으로 분리하기(크루스칼 알고리즘 미세팁)

1. 문제 1647번: 도시 분할 계획 (acmicpc.net) 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 2. 풀이 입력 자체가 "임의의 두 집 사이에 경로가 항상 존재하는 입력이 주어진다"라고 되어있는데 맨 처음에는 모든 정점에 대하여 서로 연결된 하나의 그래프 집합이 주어지는데.. 여기서 몇개의 간선을 선택해서 두 집합으로 분리하라는 문제 이 때 선택된 간선의 가중치 합이 최소가 되도록 만들어야한다 최소 스패닝 트리 이전에 그냥 진짜 단순하게 생각해보면, 초기에..