题解 | #最小生成树#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 返回最小的花费代价使得这n户人家连接起来
# @param n int整型 n户人家的村庄
# @param m int整型 m条路
# @param cost int整型二维数组 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
# @return int整型
#
class Solution:
    def miniSpanningTree(self , n: int, m: int, cost: List[List[int]]) -> int:
        # write code here
        # Kruskal算法
        
        # 构建并查集
        u = UnionFindSet(n)
        # 边按权重升序排序
        cost = sorted(cost, key = lambda x: x[2])
        # 遍历每条边
        res = 0
        for i in range(m):
            [Fr,To,weigh] = cost[i]
            if u.find(Fr) == u.find(To):
                continue
            res += weigh
            u.union(Fr, To)
        return res
    
class UnionFindSet:
    def __init__(self, n):
        self.par = dict((i,i) for i in range(1, n+1))
        
    def find(self, node):
        if node != self.par[node]:
            self.par[node] = self.find(self.par[node])
        return self.par[node]
    
    def union(self,x,y):
        self.par[self.find(y)] = self.find(x)