题解 | #最小生成树#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int n户人家的村庄
     * @param m int m条路
     * @param cost intvector<vector<>> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int
     */
    
    static bool cmp(vector<int>& a, vector<int>& b) {
        int n = a.size() - 1;
        int m = b.size() - 1;
        return a[n] < b[m];
    }
    int find(int a, vector<int>& p) {
        if(p[a] != a)
            p[a] = find(p[a], p);
        return p[a];
    }
    int kruskal(vector<vector<int>>& cost, vector<int>& p, int& res) {
        int n = cost.size();
        int m = cost[0].size();
        // 保证输入的每个cost为3个数值
        if(m != 3)
            return 0;
        // 记录进入集合的村庄数
        int count = 0;
        for(int i = 0; i < n; i++) {
            int a = cost[i][0];
            int b = cost[i][1];
            if(find(a, p) != find(b, p)) {
                p[find(a, p)] = find(b, p);
                count++;
                res += cost[i][2];
            }
        }
        return count;
    }
    int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
        // write code here
        int res = 0;
        // 并查集父亲数组,判断村庄是否已经进入集合
        vector<int> p(n + 1);
        sort(cost.begin(), cost.end(), cmp);
        // 初始化并查集
        for(int i = 0; i < cost.size(); i++) {
            int n1 = cost[i][0];
            int n2 = cost[i][1];
            p[n1] = n1;
            p[n2] = n2;
        }
        int count  = kruskal(cost, p, res);
        if(count == n - 1)
            return res;
        else
            return 0;
    }
};