최소신장트리(MST) 각 간선(edge)의 weight가 1이나 0이 아닌 경우에 모든 노드를 한 트리로 묶은 것(spanning tree)의 weight의 합이 최소가 되는 것을 MST (minimum spanning tree) 라 한다. 이를 구하는 방법은 union find를 쓰는 Kruskal과, Dijkstra의 변형인 Prim이 있는데, 통상 CP에서는 전자를 많이 쓴다고 한다. UnionFind Kruskal을 쓰려면 union find 자료구조를 정의해서 사용해야 한다. 다음 코드는 path compression과 union-by-rank가 모두 적용된 클래스이다. class UnionFind: def __init__(self, N: int) -> None: # N: number of ve..