题解 | #最小生成树#

class Solution {
private:
    class UF                                       //建立标准并查集，已进行路径压缩
    {
    public:
        int count;
        vector<int> parents;
        UF(int n)
        {
            this -> count = n;
            parents.resize(n);
            for(int i = 0; i < n; ++i)
            parents[i] = i;
        }
        int find(int x)
        {
            if(parents[x] != x)
            parents[x] = find(parents[x]);
            return parents[x];
        }
        bool connected(int x, int y)
        {
            int rootX = find(x);
            int rootY = find(y);
            return rootX == rootY;
        }
        void Union(int x, int y)
        {
            int rootX = find(x);
            int rootY = find(y);
            if(rootX != rootY)
            {
                parents[rootX] = rootY;
                --count;
            }
        }
        int _count()
        {
            return count;
        }
    };
public:
    int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
        UF uf(n + 1);                           //题目从1到n编号因此要使用n + 1作为参数
        int mst = 0;
        sort(cost.begin(), cost.end(), [](vector<int> a, vector<int> b){return a[2] < b[2];}); //贪心算法，将短边排在前面。
        for(vector<int> cos : cost)
        {
            int i = cos[0];
            int j = cos[1];
            if(!uf.connected(i, j))  //判断i,j是否已联通，若已经联通则不在需要Union
            {
                mst += cos[2];
                uf.Union(i, j);
            }
        }
        return uf._count() == 2 ? mst : -1;      //按正常情况此处应该等于1，但本题从1到n编号，其中0号为占位符，因此判断为等于2，其中为一个占位符加一棵树。
    }
};