题解 | #最小生成树#

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>& fa, int x) {
        if (fa[x] != x) {
            fa[x] = Find(fa, fa[x]);
        }
        return fa[x];
    }
    int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
        // write code here
        vector<int> fa(n + 1);
        for (int i = 0; i <= n; i++) {
            fa[i] = i;
        }
        sort(cost.begin(), cost.end(), [&](const vector<int>& a, const vector<int>& b) {
            return a[2] < b[2];
        });
        int ans = 0;
        for (auto& e: cost) {
            if (Find(fa, e[0]) != Find(fa, e[1])) {
                ans += e[2];
                fa[Find(fa, e[0])] = Find(fa, e[1]);
            }
        }
        return ans;
    }
};