题解 | #最小生成树Kruskal#

class Solution {
    static bool cmp(vector<int>& v1, vector<int>& v2) {
        return v1[2] < v2[2];
    }
    vector<int> p;
    int find(int x)
    {
        if(x != p[x]) p[x] = find(p[x]);
        return p[x];
    }
  public:
    int miniSpanningTree(int n, int m, vector<vector<int>>& cost) {
        p = vector<int>(n + 1);
        for(int i = 0; i <= n; i ++)
        {
            p[i] = i;
        }
        sort(cost.begin(), cost.end(), cmp);
        int res = 0, cnt = 0;
        for(int i = 0; i < m; i ++)
        {
            int a = find(cost[i][0]), b = find(cost[i][1]);
            if(a != b)
            {
                p[a] = b;
                res += cost[i][2];
                cnt ++;
            }
        }
        if(cnt == n - 1) return res;
        return -1;
    }
};