题解 | #最小生成树#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int n户人家的村庄
     * @param m int m条路
     * @param cost intvector<vector<>> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int
     */
    int find(vector<int>& parent,int index){//并查集，用来寻找集合的代表节点的函数
        if(parent[index]==index) return index;
        else return find(parent,parent[index]);
    }
  
    int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
        sort(cost.begin(),cost.end(),[](vector<int> x1,vector<int>x2){//从小到大排序
            return x1[2]<x2[2];
        });
        vector<int> parent(n+1);
        for(int i = 0;i<=n;i++){//初始化，按道理从1开始就行
            parent[i] = i;
        }
        int res = 0;
        int ans = 0;
        for(int i = 0;i<m;i++){
            int i1 = find(parent,cost[i][0]);
            int i2 = find(parent,cost[i][1]);
            if(i1!=i2){
                parent[i1] = parent[i2];//代表节点的替换
                res+=cost[i][2];
                ans+=1;
            }
            if(ans == n-1)break;//n个点都有连接了
        }
        if(ans<n-1) return -1;
        return res;
    }
};

参考教程：很好的教程哦 https://blog.csdn.net/qq_36530992/article/details/118891787?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522164774135016782184634265%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=164774135016782184634265&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-2-118891787.142^v2^pc_search_result_control_group,143^v4^control&utm_term=leetcode%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91&spm=1018.2226.3001.4187