PS
백준 1647. 도시 분할 계획
tose33
2022. 7. 11. 12:58
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를 만들고, MST에서 가중치가 가장 큰 간선을 빼주면 문제에서 원하는 두 개의 그래프가 된다.