[link](https://leetcode.com/problems/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.

---

Create an adjacency dictionary adj to represent the graph, where each point index maps to a list of tuples containing the distance to other points and their corresponding point indices. The adjacency list only includes pairs of points that have not been considered before, as the distance between any two points is symmetric.

Iterate through all pairs of points using two nested loops. For each pair of points points[i] and points[j], calculate the Manhattan distance dist between them. Then, add both points to each other's adjacency list along with their calculated distance.

Initialize the result variable res to store the minimum cost and create a min-heap minHeap with a tuple (0, 0) where the first element is the cost and the second element is the index of the starting point (index 0).

Initialize an empty set visit to keep track of visited points.

While the number of visited points is less than the total number of points:
a. Pop the tuple (cost, point) from the minHeap.
b. If the current point has already been visited, skip to the next iteration.
c. Add the cost to the result res.
d. Mark the current point as visited by adding it to the visit set.
e. For each neighbor point neiPoint and its corresponding distance neiCost in the adjacency list for the current point:

If the neighbor point has not been visited, push a tuple (neiCost, neiPoint) into the min-heap. Return the final result res.

#### Solution 1

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        adj = collections.defaultdict(list)
        for i in range(len(points)):
            x1, y1 = points[i]
            for j in range(i + 1, len(points)):
                x2, y2 = points[j]
                dist = abs(x1 - x2) + abs(y1 - y2)
                adj[i].append([dist, j])
                adj[j].append([dist, i])
        res = 0
        minHeap = [(0, 0)]
        visit = set()
        while len(visit) < len(points):
            cost, point = heapq.heappop(minHeap)
            if point in visit:
                continue
            res += cost
            visit.add(point)
            for neiCost, neiPoint in adj[point]:
                if neiPoint not in visit:
                    heapq.heappush(minHeap, (neiCost, neiPoint))
            
        return res
        

O(T): O(N^2 * logN)
O(S): O(N + E)

---

The UnionFind class is defined to manage the union-find operations for disjoint sets. Each element in the disjoint set is represented by a parent (par) and a rank (rank). The class provides methods find to find the representative of a set and union to perform a union operation between two sets. The distance function calculates the Manhattan distance between two points p1 and p2.

The main minCostConnectPoints function starts by creating a min-heap minHeap to store edges, where each edge is represented as a tuple (distance, index1, index2). All possible edges are added to the min-heap.

Initialize a UnionFind object uf to manage the connected components and a variable res to store the final result. Initialize an empty list mst to store the minimum spanning tree (MST) edges.

While the number of edges in the MST is less than n - 1 (where n is the number of points):

a. Pop the edge with the minimum distance from the minHeap.
b. If the two endpoints of the edge are not in the same connected component, perform a union operation using the uf object.
c. Add the edge to the mst list and update the result res by adding the distance of the edge.

Return the final result res, which represents the minimum cost to connect all points using the minimum spanning tree.

#### Solution 2

class UnionFind():
    def __init__(self, n):
        self.par = {}
        self.rank = {}

        for i in range(n):
            self.par[i] = i
            self.rank[i] = 0


    def find(self, n):
        p = self.par[n]
        while p != self.par[p]:
            self.par[p] = self.par[self.par[p]]
            p = self.par[p]
        return p


    def union(self, n1, n2):
        p1, p2 = self.find(n1), self.find(n2)
        if p1 == p2:
            return False
        if self.rank[p1] > self.rank[p2]:
            self.par[p2] = p1
        elif self.rank[p1] < self.rank[p2]:
            self.par[p1] = p2
        else:
            self.par[p1] = p2
            self.rank[p2] += 1
        return True
        

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        def distance(p1, p2):
            return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
        
        minHeap = []
        n = len(points)
        for i in range(n):
            for j in range(i + 1, n):
                heapq.heappush(minHeap, (distance(points[i], points[j]), i, j))

        uf = UnionFind(n)
        res = 0 
        mst = []
        
        while len(mst) < n - 1:
            w, n1, n2 = heapq.heappop(minHeap)
            if not uf.union(n1, n2):
                continue
            res += w
            mst.append([n1, n2])
    
        return res

O(T): O(E log E + E α(V))
O(S): O(N + E)