# Min Cost to Connect All Points

``````class Solution {
class Triple{
int from;
int to;
int weight;
public Triple(int from, int to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
}
private static class DSU {
int[] ranks;
int[] parents;
public DSU(int size) {
this.ranks = new int[size];
Arrays.fill(ranks, 1);
this.parents = new int[size];
for(int i = 0; i < size; i++){
this.parents[i]= i;
}
}

int get(int v) {
if (v == parents[v]) return v;
return parents[v] = get(parents[v]);
}

boolean union(int a, int b) {
a = get(a);
b = get(b);

if (a == b) return false;

if (ranks[a] < ranks[b]) {
int tmp = a;
a = b;
b = tmp;
}
parents[b] = a;
if (ranks[a] == ranks[b]) ++ranks[a];
return true;
}
}

public int minCostConnectPoints(int[][] points) {
int n = points.length;
PriorityQueue<Triple> g = new PriorityQueue<>((a, b) -> (a.weight - b.weight));
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++) {
}
}
DSU dsu = new DSU(n);
int res = 0;
while (!g.isEmpty()) {
Triple t = g.poll();
if (dsu.get(t.from) == dsu.get(t.to))
continue;
dsu.union(t.from, t.to);
res += t.weight;
}
return res;
}
public int cost (int[][] p, int i,  int j) {
return Math.abs(p[i][0] - p[j][0]) + Math.abs(p[i][1] - p[j][1]);
}
}``````