1135.最低成本联通所有城市

付费题

一、最小生成树（Kruskal算法）

cost视为边的权值，连通所有城市的最小成本即最小生成树的权值之和

#并查集实现略
class Solution:
    def minimumCost(self, n: int, connections: List[List[int]]) -> int:      
        uf = UnionFind(n+1) # 0号结点不用
        res = 0 #最终成本
        # 将connections按权值排序，然后从小到大遍历
        connections.sort(key = lambda x : x[2])	
        for a, b, w in connections:
            if not uf.isConnected(a, b):	#若ab不连通，则将其加入生成树（即连接）
                uf.union(a, b)
                res += w	#加上权值
        return res if uf.count == 2 else -1	#因为0不用，所有最终连通分量数为2才表示存在最小生成树