class Solution {
public class Edge{
int len;//边长度
int x;//顶点1
int y;//顶点2
public Edge(int len,int x,int y){
this.len = len;
this.x = x;
this.y = y;
}
}
public int minCostConnectPoints(int[][] points) {
int n = points.length;//顶点个数
List<Edge> edges = new ArrayList<Edge>();
UnionFind uf = new UnionFind(n);
for(int i =0;i<n-1;i++){
for(int j=i+1;j<n;j++){
int[] pointi = points[i];
int[] pointj = points[j];
int len = Math.abs(pointi[0] - pointj[0]) + Math.abs(pointi[1] - pointj[1]);
edges.add(new Edge(len,i,j));
}
}
Collections.sort(edges, new Comparator<Edge>() {
public int compare(Edge edge1, Edge edge2) {
return edge1.len - edge2.len;
}
});
int sum = 0;
int index = 0;
while(uf.count>1){
Edge edge= edges.get(index);
boolean flag = uf.Union(edge.x,edge.y);
if(flag == true)
sum += edge.len;
index+=1;
}
return sum;
}
public class UnionFind{
int[] parent;
int count;
public int getCount(){
return count;
}
public UnionFind(int n){
parent = new int[n];
count = n;
for(int i =0;i<n;i++)
parent[i] = i;
}
public int find(int x){
if(parent[x] != x)
parent[x] = find(parent[x]);
return parent[x];
}
public boolean Union(int x,int y){
int rootX = find(x);
int rootY = find(y);
if(rootX == rootY)
return false ;
parent[rootX] = rootY;
count -= 1;
return true;
}
}
}