题解 | #最小生成树#

#include <cmath>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int整型 n户人家的村庄
     * @param m int整型 m条路
     * @param cost int整型vector<vector<>> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int整型
     */
    int n = 5003;
    int father[5003];
    //初始化并查集
    void init(){
        for(int i=0;i<n;i++){
            father[i] = i;
        }
    }
    //并查集里面寻根
    int find(int u){
        if(father[u] == u){
            return u;
        }else{
            father[u] = find(father[u]);
            return father[u];
        }
    }
    //将 u->v 加入并查集
    void join(int u,int v){
        u = find(u);
        v = find(v);
        if(u == v) return;
        father[v] = u;
    }
    //判断 u v 是否为同一个根
    bool same(int u,int v){
        u = find(u);
        v = find(v);
        return u == v;
    }
    
    int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
        // write code here
        int ans = 0;
        //kruskal
        // 对邻接表按照边权递增排序
        sort(cost.begin(),cost.end(),[](vector<int>&a,vector<int>&b){
            return a[2] < b[2];
        });
        // 从最小的边开始遍历
        init();
        for(auto vec:cost){
            // 检查边的两边是否在同一个并查集中
            if(!same(vec[0],vec[1])){
                ans += vec[2];
                join(vec[0], vec[1]);
            }
        }
        
        return ans;
    }
};

kruskal算法+并查集