최소 신장 트리. [6497]

[1. 문제 설명]

[2. 풀이 접근]

함정(?)

입력이 주어지는 방식
=> 보통 몇개의 TC 가 있고, TC 개수 만큼 반복 수행
=> 이 문제에서는 특정 입력이 들어오기 전 까지가 모두 TC 이다.
u -> v 로 가는 경로가 여러 가지 일 수 있다.
=> 이 때,
=> 우선순위 큐 사용이 없으면, u <-> v 로 연결되는 edge 의 cost 를 최소 값을 쓰도록 해야한다.
=> map 을 이용해서, 최소 cost 추적이 필요 함.
=> 문제에서 node 가 최대 2,000,000 개 이므로, 인접 행렬을 사용 할 수 없다.
=> 이 문제에서는 mst 를 구해야 하므로, 우선순위 큐를 사용하므로, 위와 같이 할 필요는 없다.

[3. 코드]

test_kernelv2