题解 | 最小生成树

#include <algorithm>
class Solution {
  public:
    /**
     n 户人家 → n 个点（顶点）
     m 条路 → m 条边，每条边有一个权重（修路成本）
     要让所有人家连起来（形成连通图），而且总成本最低 → 最小生成树（Minimum Spanning Tree, MST）
	 
     生成树:包含所有顶点,且n-1条边,也就是一条线连接所有顶点;
	 最小生成树:采用的边的代价和最小
	
     Kruskal 的核心思想是一个贪心策略：
        每次挑最便宜的路(按边的距离排序)，利用并查集, 如果两个节点还没有连接(不在一个集合里)，就修它(放到一个集合,累计成本)，直到所有村庄连通(n-1个边被使用)。
     */
    struct UnionFind{
        vector<int> parent, rank;

        UnionFind(int n){
            parent.resize(n);    //对头节点进行初始化
            rank.resize(n, 0);   //对集合的高度进行初始化

            for(int i=0; i<n; i++){
                parent[i] = i;   //每个的头节点初始化为自己,表示自己是一个集合
            }
        }

        int find(int x){  //查找数x的头节点是多少,并进行路径压缩(找到后赋值)
            if(parent[x] != x){  //若是下属
                parent[x] = find(parent[x]);  //如果 
            }
            return parent[x];
        }

        // 合并两个集合
        bool unite(int x, int y){
            int root_x = find(x);
            int root_y = find(y);

            if(root_x == root_y)return false;  //两个城市已经在同一个集合里了,不需要合并

            // 把树高度低的那部分,放到高的集合下
            if(rank[root_x] < rank[root_y]){
                parent[root_x] = root_y;  //改变头节点即可
            }else if(rank[root_y] < rank[root_x]){
                parent[root_y] = root_x;
            }else{
                parent[root_y] = root_x;  //一样高时,作为两个集合的头的高度+1;
                rank[root_x]++;
            }

            return true;
        }
    };

    int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
        sort(cost.begin(), cost.end(), [](vector<int>& a, vector<int>& b){
            return a[2] < b[2];
        });  //按照成本从小到大排序

        UnionFind uf(n);  //创建并查集

        int totalCost = 0;  //答案:总长度
        int edgeUsed = 0;  //记录已经采用的边,到n-1时停止

        //  从最短边开始遍历,尝试不同集合
        for(int i=0; i<m; i++){
            int u = cost[i][0]-1;  //头节点,cost里的节点是从1开始的,而我的并查集是从0开始的
            int v = cost[i][1]-1;  //尾
            int w = cost[i][2];  //代价

            if(uf.unite(u, v)){
                totalCost += w; 
                edgeUsed ++;
                if( edgeUsed == n-1){
                    break;
                }
            }
        }

        return edgeUsed==n-1 ? totalCost:-1;
    }
};