题解 | #最小生成树#

from math import cos


# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 返回最小的花费代价使得这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
        cost = sorted(cost,key = lambda x:x[2],reverse=True)
        father_dict = {}
        size_dect = {}
        sum = 0
        for node in range(n):
            father_dict[node]=node
            size_dect[node]=1

        #递归查找根节点（父节点是自己的节点）
        def find(node):
            father = father_dict[node]
            if (node !=father):
                if father!=father_dict[father]:
                    size_dect[father]-=1
                father = find(father)
            father_dict[node] = father

            return father
        
        # 查看两个节点是否在一个集合内
        def is_same_set(node_a,node_b):
            if (find(node_a) is None) or (find(node_b) is None):
                return 0
            else:
                return find(node_a)==find(node_b)
        
        # 将两个集合合并在一起（只需合并根节点），size_dect大吃小
        def union(node_a,node_b):
            
            a_root = find(node_a)
            b_root = find(node_b)
            if a_root is None or b_root is None:
                return
            # 两个节点不在同一个集合中，则合并两个集合
            a_size = size_dect[a_root]
            b_size = size_dect[b_root]

            if (a_size>=b_size):
                father_dict[b_root]=a_root
                size_dect[a_root]=a_size+b_size
            else:
                father_dict[b_root] = a_root
                size_dect[a_root] = a_size + b_size

        while cost:
            arr = cost.pop()
            u = arr[0]-1
            v= arr[1]-1

            flag = is_same_set(u,v)
            if not flag:
                union(u,v) 
                sum = sum+arr[2]       
        
        return sum

# 难点：怎么判断这两个点在同一颗树上

看别人的思路做起来就是飞快，难的始终是算法哈哈哈：

附一个参考链接：https://blog.csdn.net/qq_41750911/article/details/125104624