描述

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

costcost 为一个二维数组，每个元素是一个长度为 3 的一维数组 aa ， a[0]a[0] 和 a[1]a[1] 表示村庄 a[0]a[0] 和村庄 a[1]a[1] 有一条路，修这条路的成本价格为 a[2]a[2] 。

每户之间可能有多条道路连接，但不可能自己与自己相连。

数据范围: 1 \le n \le 5 \times 10^31≤n≤5×103 ， 1 \le m \le 5 \times 10^51≤m≤5×105 ， 1 \le a[2] \le 10^41≤a[2]≤104
进阶： 时间复杂度 O(n+mlogm)O(n+mlogm) ， 空间复杂度 O(n)O(n)

示例1

输入： 
3,3,[[1,3,3],[1,2,1],[2,3,1]]
复制
返回值： 
2
复制

示例2

输入： 
2,1,[[1,2,1]]
复制
返回值： 
1
解题思路：
1、注意输入参数是二维数组，每一维里存了三个数
2、使用贪心+并查集
贪心：将输入参数按照花费大小升序排序，从小的花费开始遍历，连通完所有村庄后即为花费最小值
并查集：道路是相互连着，所以是无向图，只要判断连通性，将所有村庄都连起来就可以了 

class UF {
public:
    vector<int> parent;
    vector<int> len;
    int cnt = 0;
    UF(int n) {
        parent.resize(n+1);
        len.resize(n+1);
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
            len[i] = 1;
        }
        cnt = n+1;
    }

    int find(int x) {
        while (x != parent[x]) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    void connect(int x, int y)
    {
        int rootx = find(x);
        int rooty = find(y);
        if (rootx == rooty) return;
        if (len[rootx] < len[rooty]) {
            parent[rootx] = rooty;
            len[rooty] += len[rootx];
        } else {
            parent[rooty] = rootx;
            len[rootx] += len[rooty];
        }
        cnt--;
    }

    bool isConnect(int x, int y) {
        int rootx = find(x);
        int rooty = find(y);
        if (rootx == rooty) {
            return true;
        } else {
            return false;
        }
    }

    int getCount() {
        return cnt;
    }
};
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int n户人家的村庄
     * @param m int m条路
     * @param cost intvector<vector<>> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int
     */
    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];});
        int costLen = cost.size();
        UF* uf = new UF(n);
        int res = 0;
        for (int i = 0; i < costLen; i++) {
            int from = cost[i][0];
            int to = cost[i][1];
            int value = cost[i][2];
            if (uf->isConnect(from, to)) continue;
            uf->connect(from, to);
            res += value;
        }
        if (uf->getCount() == 2) { // 0和其他非零的连通，一共还有两个
            return res;
        } else {
            return -1;
        }
    }
};