C++刷leetcode（1584. 连接所有点的最小费用）【kruskal算法】

糖逗

题目描述：

给你一个points 数组，表示 2D 平面上的一些点，其中 points[i] = [xi, yi] 。

连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 ：|xi - xj| + |yi - yj| ，其中 |val| 表示 val 的绝对值。

请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。

 

示例 1：



输入：points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
输出：20
解释：

我们可以按照上图所示连接所有点得到最小总费用，总费用为 20 。
注意到任意两个点之间只有唯一一条路径互相到达。
示例 2：

输入：points = [[3,12],[-2,5],[-4,1]]
输出：18
示例 3：

输入：points = [[0,0],[1,1],[1,0],[-1,1]]
输出：4
示例 4：

输入：points = [[-1000000,-1000000],[1000000,1000000]]
输出：4000000
示例 5：

输入：points = [[0,0]]
输出：0
 

提示：

1 <= points.length <= 1000
-106 <= xi, yi <= 106
所有点 (xi, yi) 两两不同。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/min-cost-to-connect-all-points
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
private:
    vector<int> father;
public:
    struct Edge{
        int a1, a2, distance;
        bool operator < (const Edge & other) const{
            return this -> distance < other.distance;
        }
    };  
    int find_root(int a){
        if(father[a] != a)return find_root(father[a]);
        return a;
    }
    void unite(int a, int b){
        int temp1 = find_root(a);
        int temp2 = find_root(b);
        if(temp1 != temp2){
            father[temp1] = temp2;
        }
        return;
    }

    int solution(int len, vector<Edge>& store){
        //建立父亲集合
        father = vector<int>(len, 0);
        for(int i = 0; i < len; i++){
            father[i] = i;
        }
        int res = 0;
        for(auto cha : store){
            int temp1 = find_root(cha.a1);
            int temp2 = find_root(cha.a2);
            if(temp1 != temp2){
                res += cha.distance;
                unite(temp1, temp2);
                len--;//当所有点都在一棵树的时候停止
                if(len == 1)return res;
            }
        }
        return res;
    }
    int minCostConnectPoints(vector<vector<int>>& points) {
        int len = points.size();
        vector<Edge> store;
        for(int i = 0; i < len; i++){
            for(int j = i; j < len; j++){
                store.push_back({i, j, 
                abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])});
            }
        }
        sort(store.begin(), store.end());
        return solution(len, store);
    }
};

参考链接：https://leetcode-cn.com/problems ... ie-da-by-yizhe-shi/
学习视频：https://www.bilibili.com/video/B ... 3053730826471308736