# Min Cost to Connect All Points

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.

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

Constraints:

• `1 <= points.length <= 1000`
• `-106 <= xi, yi <= 106`
• All pairs `(xi, yi)` are distinct.

SOLUTION:

``````import heapq
from collections import defaultdict

class Solution:
def union(self, parent, i, j):
parent[i] = j

def getParent(self, parent, i):
if i not in parent:
return i
return self.getParent(parent, parent[i])

def isCycle(self, graph, n):
parent = {}
for i in graph:
for j in graph[i]:
x = self.getParent(parent, i)
y = self.getParent(parent, j)
if x == y:
return True
self.union(parent, x, y)
return False

def minCostConnectPoints(self, points):
n = len(points)
edges = []
for i in range(n):
for j in range(i + 1, n):
a, b = points[i]
c, d = points[j]
cost = abs(c - a) + abs(d - b)
heapq.heappush(edges, (cost, i, j))
graph = defaultdict(set)
rem = n - 1
op = 0
while rem > 0:
if len(edges) > 0:
currdist, i, j = heapq.heappop(edges)