백준 25545 - MMST (C++)

문제 문제 링크 BOJ 25545 - MMST 문제 요약 모든 간선의 가중치가 다른 무향 연결 그래프가 주어진다. 이 그래프의 $MMST$를 구해보자.

제한 TL : $1$ sec, ML : $1024$ MB $1 ≤ N ≤ 200,000$ $N - 1 ≤ M ≤ 500,000$ $-10^9 ≤ C_i ≤ 10^9$ 알고리즘 분류 그래프 이론(graphs) 최소 스패닝 트리(minimum spanning tree) 풀이 얼핏 잘못 보면 삽질하기 쉬운 문제인데, $mst$의 본질을 안다면 굉장히 쉬워진다. "모든 간선의 가중치가 다른 무향 연결 그래프가 주어질 때," 위 조건을 유의한 채 얻을 수 있는 정보를 나열하면 다음과 같다.

$M == N - 1$일 때는 $MMST$가 존재할 수 없다. 반대로 $N.....