package question;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class Question1584 {
 public int minCostConnectPoints(int[][] points) {
 Queue<Edge> queue = new PriorityQueue<>(new Comparator<Edge>() {
 @Override
 public int compare(Edge o1, Edge o2) {
 return o1.l-o2.l;
 }
 });
 for (int i = 0; i < points.length; i++) {
 for (int j = i+1; j < points.length; j++) {
 queue.add(new Edge(i,j,man(points[i][0], points[i][1], points[j][0], points[j][1])));
 }
 }
 int index=0;
 int n=points.length-1;
 int res=0;
 UnionFind unionFind=new UnionFind(points.length);
 while (index<n) {
 Edge poll = queue.poll();
 if (!unionFind.merge(poll.a, poll.b)) {
 res+=poll.l;
 index++;
 }
 }
 return res;
 }

 private class UnionFind {
 int[] p;

 public UnionFind(int n) {
 p=new int[n];
 for (int i = 0; i < p.length; i++) {
 p[i]=i;
 }
 }

 public boolean merge(int a, int b) {
 a=find(a);
 b=find(b);
 if (a==b) return true;
 p[b]=a;
 return false;
 }

 private int find(int x) {
 if (x==p[x]) return x;
 p[x]=find(p[x]);
 return p[x];
 }
 }

 private int man(int x1, int y1, int x2, int y2) {
 return Math.abs(x1-x2)+Math.abs(y1-y2);
 }
}

class Edge {
 int a,b,l;

 public Edge(int a, int b, int l) {
 this.a = a;
 this.b = b;
 this.l = l;
 }
}