---
description: basically use union find
---

# 1584. Min Cost to Connect All Points

```java
class Solution {
    class Edge {
        int x;
        int y;
        int w;
        Edge(int x, int y, int w) {
            this.x = x;
            this.y = y;
            this.w = w;
        }
    }
    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        List<Edge> edges = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                edges.add(new Edge(i, j, Math.abs(points[i][0] - points[j][0]) +  Math.abs(points[i][1] - points[j][1])));
            }
        }
        Collections.sort(edges, (a, b) -> a.w - b.w);

        int result = 0;
        UnionFind uf = new UnionFind(n);
        for (Edge e : edges) {
            if (!uf.union(e.x, e.y)) {
                continue;
            }
            result += e.w;
        }
        return result;
    }
    class UnionFind {
        int[] parent;
        UnionFind(int n) {
            this.parent = new int[n];
            for (int i = 0; i < n; i++) {
                this.parent[i] = i;
            }
        }
        public boolean union(int i, int j) {
            int x = find(i);
            int y = find(j);
            if (x != y) {
                parent[x] = y;
                return true;
            }
            return false;
        }
        private int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
    }
}
```
