https://www.acmicpc.net/problem/1922

최소신장트리(Minimum spanning tree)를 사용하면 됩니다. 저는 크루스칼 알고리즘으로 구현을 했고, 프림 알고리즘의 시간 복잡도가 조금 더 효율적이지만 Edge의 수가 100000이기 때문에 어느 것을 사용해도 시간 내에 답을 얻을 수 있습니다.

Union-find때 경로압축을 해주지 않으면 시간초과가 날 수 있기 때문에 find 과정에서 경로를 계속 압축시켜줘야합니다.

https://github.com/encrypted-def/BOJ/blob/master/1922.cpp