题解 | #最小生成树#

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int整型 n户人家的村庄
     * @param m int整型 m条路
     * @param cost int整型vector<vector<>> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int整型
     */
    static bool cmp(const vector<int>& x, const vector<int>& y) {
        return x[2] < y[2];
    }
    int find(vector<int>& parent, int x) {
        if (parent[x] != x)
            parent[x] = find(parent, parent[x]);
        return parent[x];
    }
    int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
        vector<int> parent(n + 1);
        for (int i = 0; i <= n; i++)
            parent[i] = i;
        sort(cost.begin(), cost.end(), cmp);
        int res = 0;
        int count = 0;
        for (int i = 0; i < cost.size(); i++) {
            int px = cost[i][0];
            int py = cost[i][1];
            if (find(parent, px) != find(parent, py)) {
                res += cost[i][2];
                parent[find(parent,px)] = find(parent,py);//容易错
                count++;
            }
            if (count == n - 1)
                break;
        }
        return res;
        // write code here
    }
};