题解 | #最小生成树#

//kruscal
class Solution {
public:
    int find(unordered_map<int,int>& parent,int& x){//传引用更快，特别是递归中
        /*1
        while(parent[x]!=x){  //向上找到最高的父亲(父亲为自己)
            x=parent[x];//parent[parent[x]];每次执行链式查询，不改变p[x]
        }
        return parent[x];
    }*/
        /*2
        int n=parent[x];
        if(parent[x]!=x)  //向上找到最高的父亲
            n=find(parent,parent[x]);//每次执行链式查询，不改变p[x]
        return n;//parent[x];
    }*/
           if(parent[x]!=x)  //向上找到最高的父亲
            parent[x]=find(parent,parent[x]);
            //每次执行改变p[x]为最高的父亲，缩短路径
        return parent[x];
    }
        
        
    int miniSpanningTree(int n, int m, vector<vector<int>>& cost) {
        unordered_map<int,int> parent;
        for(int i=0;i<=n;i++)//初始父亲设置为自己
            parent[i]=i;
        sort(cost.begin(),cost.end(),[](vector<int>& a, vector<int>& b) {
        return a[2]<b[2];   //边权递增排序
    });
        int res=0;
        for(int i=0;i<cost.size();i++){
            int x=cost[i][0];
            int y=cost[i][1];
            int z=cost[i][2];
            int px=find(parent,x);//查找x的最上边父亲
            int py=find(parent,y);// 查找y的最上边父亲
            if(px!=py){//如果二者不在同一个集合
                res+=z;//边加入
                parent[px]=py;//设置二者在同一个集合
            }
        }
        return res;
    }
};