You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi].

The cost of connecting two points [xi, yi] and [xj, yj] is the manhattan distance between them: |xi - xj| + |yi - yj|, where |val| denotes the absolute value of val.

Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.

&nbsp;
Example 1:

Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20
Explanation: 

We can connect the points as shown above to get the minimum cost of 20.
Notice that there is a unique path between every pair of points.


Example 2:

Input: points = [[3,12],[-2,5],[-4,1]]
Output: 18


&nbsp;
Constraints:


	1 &lt;= points.length &lt;= 1000
	-106 &lt;= xi, yi &lt;= 106
	All pairs (xi, yi) are distinct.


class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:

        cost = 0
        heap = []

        #set to store past points to prevent cycle
        visited = set([0])

        #i == the index of current point
        i = 0

        while len(visited) < len(points):
            #Add all costs from current point to unreached points to min heap
            for j in range(len(points)):
                if j == i or j in visited:
                    continue
                distance = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
                heapq.heappush(heap, (distance, j))

            #Add new min cost edge
            while True:
                dist, point = heapq.heappop(heap)
                if point not in visited:
                    cost += dist
                    #Add point to visited to prevent cycle
                    visited.add(point)
                    #Update point
                    i = point
                    break

        return cost
class Solution {
	public int minCostConnectPoints(int[][] points) {
		int n = points.length;
		PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->a[0]-b[0]);
		for(int i = 0; i < n; i++) {
			for(int j = i + 1; j < n; j++) {
				pq.add(new int[]{calDis(points,i,j),i,j});
			}
		}
		int c = 0, ans = 0;
		UnionFind uf = new UnionFind(n);
		while(c < n-1){
			int[] cur = pq.poll();
			if(uf.find(cur[1]) != uf.find(cur[2])) {
				ans += cur[0];
				uf.union(cur[1],cur[2]);
				c++;
			}
		}
		return ans;
	}
	private int calDis(int[][] points, int a, int b) {
		return Math.abs(points[a][0] - points[b][0]) + Math.abs(points[a][1] - points[b][1]);
	}
	class UnionFind{
		int[] parent;
		UnionFind(int n){
			this.parent = new int[n];
			for(int i=0;i<n;i++)parent[i]=i;
		}
		public int find(int u){
			if(parent[u]!=u)parent[u] = find(parent[u]);
			return parent[u];
		}
		public void union(int u, int v){
			parent[find(u)] = parent[find(v)];
		}
	}
}
class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);

        int n = points.size();
        priority_queue<vector<int>> q;
        unordered_set<int> vis;
        int ans = 0;
        q.push({0,0,0});
        vector<int> cur;
        while(!q.empty() && vis.size()<n){
            cur = q.top(); q.pop();
            if(vis.count(cur[2]))continue;
            ans += -cur[0];
            vis.insert(cur[2]);
            for(int i=0;i<n;i++){
                if(!vis.count(i)){
                    int d = abs(points[cur[2]][0] - points[i][0]) +
                        abs(points[cur[2]][1] - points[i][1]);
                    q.push({-d,cur[2],i});
                }
            }
        }
        return ans;
    }
};
/**
 * @param {number[][]} points
 * @return {number}
 */
//By Kruskal Approach
let union_find,mapping_arr,count,maxCost,rank
const find=(root)=>{
    if(union_find[root]===root)return root;
    return union_find[root]= find(union_find[root]);
}
const union=([src,dst,d])=>{
    let rootX=find(src);
    let rootY=find(dst);
    if(rootX!=rootY){
        if(rank[rootX]<rank[rootY]){
            union_find[rootX]=rootY;
        }else if(rank[rootX]>rank[rootY]){
            union_find[rootY]=rootX;
        }else{
            union_find[rootY]=rootX;
            rank[rootX]++;
        }
        count--;
        maxCost+=d;
    }
    
    
}
var minCostConnectPoints = function(points) {
    let edges=[];
    union_find=[];
    rank=[];
    maxCost=0;
    count=points.length;
    for(let i=0;i<points.length;i++){
        union_find[i]=i;
        rank[i]=1
        let src=points[i];
        for(let j=i+1;j<points.length;j++){
            let dst=points[j];
            let d= Math.abs(src[0]-dst[0])+Math.abs(src[1]-dst[1])
            edges.push([i,j,d]);
        }
    }
    edges.sort((a,b)=>a[2]-b[2])
    for(let i=0;i<edges.length;i++){
        if(count>1)
        union(edges[i]);
    }

    return maxCost;
    
};
Min Cost to Connect All Points