5513. 连接所有点的最小费用 kruskal

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

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

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

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

思路：标准kruskal
注意，变量应放在solution函数内，否则样例与样例之间会没有更新。

const int maxn = 1005;
struct edge{
    int u, v, dis;
    edge(int u, int v, int dis) : u(u), v(v), dis(dis){}
    bool operator <(const edge &obj) const{
        return dis < obj.dis;
    }
};

int fa[maxn];
int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void unionn(int x, int y) {
    int xx = find(x);
    int yy = find(y);
    fa[xx] = yy;
}
bool same(int x, int y) {
    return find(x) == find(y);
}

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        
        int n = points.size();
      //edges应放在minCostConnectPoints内
        vector <edge> edges;
        for (int i = 0; i < n; i++) {
            fa[i] = i;
        }

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int dis = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
                edges.push_back(edge(i, j, dis));
            }
        }

        sort(edges.begin(), edges.end());

        int ans = 0;
        for (int i = 0; i < edges.size(); i++) {
            int u = edges[i].u;
            int v = edges[i].v;
            int dis = edges[i].dis;
            if (!same(u, v)) {
                ans += dis;
                unionn(u, v);
            }
        }

        return ans;
    }
};

5513. 连接所有点的最小费用 kruskal

原文：https://www.cnblogs.com/xgbt/p/13661180.html