求最小生成树有两种常见的算法：Prim\text{Prim}Prim 和 Kruskal\text{Kruskal}Kruskal。 稠密图上前者快，否则后者快。 显然这道题不是稠密图，所以我使用了 Kruskal\text{Kruskal}Kruskal。 其实是我太蒻了，不会Prim Kruskal\text{Kruskal}Kruskal 的基本思想是贪心，对所有的边按边权进行排序，逐个判断，如果边的两端在新图中不连通，则将边加入新图。 通常使用并查集维护点的连通性。 基于并查集的 Kruskal\text{Kruskal}Kruskal 算法如下。