题解 | #最小生成树#

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