题解 | 最小生成树

import re
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 返回最小的花费代价使得这n户人家连接起来
# @param n int整型 n户人家的村庄
# @param m int整型 m条路
# @param cost int整型二维数组 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
# @return int整型
#

class Union:
    def __init__(self, n: int):
        self.parent = list(range(n + 1))  # 父节点数组
        self.rank = [1] * (n + 1)  # 秩数组
    def find(self, x):
        if self.parent[x] == x:
            return x
        return self.find(self.parent[x])
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return
        if self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
            self.rank[root_x] += self.rank[root_y]
        else:
            self.parent[root_x] = root_y
            self.rank[root_y] += self.rank[root_x]
    def connection(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        return root_x == root_y
    
    
class Solution:
    def miniSpanningTree(self , n: int, m: int, cost: List[List[int]]) -> int:
        # write code here
        union = Union(n)
        cost.sort(key=lambda x:x[2])
        res = 0
        for a, b, w in cost:
            if union.connection(a, b):
                continue
            res += w
            union.union(a, b)
        return res