题解 | #最小生成树#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 返回最小的花费代价使得这n户人家连接起来
# @param n int整型 n户人家的村庄
# @param m int整型 m条路
# @param cost int整型二维数组 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
# @return int整型
#
# 找根节点函数
def find(x, parent):
    if x == parent[x]:
        return x
    return find(parent[x], parent)

# 合并两个集合函数
def union(x, y, parent, rank):
    xi, yi = find(x, parent), find(y, parent)
    # if条件是让深度小的树插在深度大的树后面， 保持树的平衡，变相减小时间复杂度，合并只是if下的两行
    if rank[xi] > rank[yi]:
        parent[yi] = xi
        rank[xi] += rank[yi]
    else:
        parent[xi] = yi
        rank[yi] += rank[xi]

# 判断是否为同一根节点，用find去找根节点
def connect(x, y, parent):
    xi, yi = find(x, parent), find(y, parent)
    return xi == yi

class Solution:
    def miniSpanningTree(self , n: int, m: int, cost: List[List[int]]) -> int:
        # write code here
        parent = [i for i in range(n+1)] # 创造父节点数组
        rank = [1 for _ in range(n+1)]   # 创造树深度数组(秩数组)
        cost.sort(key=lambda x:x[2])     # 根据代价把村庄排序，优先修代价小的路
        res = 0                          # 最后返回结果(最小代价)
        for u, v, w in cost:             # u,v是路连接的两个村庄，w是代价 
            if connect(u, v, parent):    # 如果两个村庄的根节点相同(代表他们都连接了一个共同村庄)，就不要修这条路
                continue
            res += w                     # 否则需要修路，res加上修路代价
            union(u, v, parent, rank)    # 合并村庄(把B树插到A树下面，根节点变为一样)，避免再次连接
        return res