import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

class Solution {
 public int minCostConnectPoints(int[][] points) {
 // 计算所有节点的边
 List<int[]> edges = new ArrayList<>();
 // 加入边
 for (int i = 0; i < points.length; i++) {
 for (int j = i+1; j < points.length; j++) {
 edges.add(new int[]{i,j,fun(points[i][0], points[i][1], points[j][0], points[j][1])});
 }
 }
 // 排序
 edges.sort(Comparator.comparingInt(o -> o[2]));
 // 结果
 int res = 0;
 // 利用并查集计算结果
 UnionFind uf = new UnionFind(points.length);
 for (int i = 0; i < edges.size(); i++) {
 int[] cur = edges.get(i);
 // 合并两个节点,如果能合并成功就计算和
 if (uf.merge(cur[0], cur[1])) {
 res += cur[2];
 // 如果个数到了,就结束
 if (uf.getCount() == points.length) {
 break;
 }
 }
 }
 return res;
 }

 // 求和函数
 private int fun(int x1, int y1, int x2, int y2) {
 return Math.abs(x1-x2) + Math.abs(y1-y2);
 }
}

class UnionFind{
 // 父亲节点数组
 private int[] parent;
 // 排位,用于优化并查集
 private int[] rank;
 // 计数器,计算当前一共有多少未连通的
 private int count;

 // 初始化
 public UnionFind(int length){
 parent = new int[length];
 for(int i = 0; i < length; i++){
 parent[i] = i;
 }
 rank = new int[length];
 count = length;
 }

 // 找根节点,返回的是索引
 public int findRoot(int index){
 while (parent[index] != index){
 index = parent[index];
 }
 return index;
 }

 // 连接
 public boolean merge(int xIndex,int yIndex){
 int x = findRoot(xIndex);
 int y = findRoot(yIndex);
 if (x == y){
 return false;
 }
 else {
 if (rank[x] > rank[y]){
 parent[y] = x;
 }
 else if (rank[x] < rank[y]){
 parent[x] = y;
 }
 else {
 parent[y] = x;
 rank[y] += rank[x];
 }
 }
 count--;
 return true;
 }

 // 返回计数
 public int getCount(){
 return count;
 }

 // 判断两个点是否连通
 public boolean isConnect(int xIndex,int yIndex){
 return findRoot(xIndex) == findRoot(yIndex);
 }
}