描述

一个有 $n$ 户人家的村庄，有 $m$ 条路相互连接着。村里现在要修路，每条路都有一个成本价格，现在请你帮忙计算下，最少需要花费多少钱，就能让这 $n$ 户人家连接起来。

$cost$ 为一个二维数组，每个元素是一个长度为 $3$ 的一维数组 $a$ ， $a[0]$ 和 $a[1]$ 表示村庄 $a[0]$ 和村庄 $a[1]$ 有一条路，修这条路的成本价格为 $a[2]$.b每户之间可能有多条道路连接，但不可能自己与自己相连

数据范围:
$1≤n≤5×10^3$
$1≤m≤5×10^5$
$1≤a[2]≤10^4$

进阶：
时间复杂度 $O(n+mlogm)$ ， 空间复杂度 $O(n)$

示例1
输入：

3,3,[[1,3,3],[1,2,1],[2,3,1]]

返回值：

2

示例2
输入：

2,1,[[1,2,1]]

返回值：

1

Kruskal

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