<p>You are given an array <code>points</code> representing integer coordinates of some points on a 2D-plane, where <code>points[i] = [x<sub>i</sub>, y<sub>i</sub>]</code>.</p>

<p>The cost of connecting two points <code>[x<sub>i</sub>, y<sub>i</sub>]</code> and <code>[x<sub>j</sub>, y<sub>j</sub>]</code> is the <strong>manhattan distance</strong> between them: <code>|x<sub>i</sub> - x<sub>j</sub>| + |y<sub>i</sub> - y<sub>j</sub>|</code>, where <code>|val|</code> denotes the absolute value of <code>val</code>.</p>

<p>Return <em>the minimum cost to make all points connected.</em> All points are connected if there is <strong>exactly one</strong> simple path between any two points.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/08/26/d.png" style="width: 214px; height: 268px;" />
<pre>
<strong>Input:</strong> points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
<strong>Output:</strong> 20
<strong>Explanation:</strong> 
<img alt="" src="https://assets.leetcode.com/uploads/2020/08/26/c.png" style="width: 214px; height: 268px;" />
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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> points = [[3,12],[-2,5],[-4,1]]
<strong>Output:</strong> 18
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= points.length &lt;= 1000</code></li>
	<li><code>-10<sup>6</sup> &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= 10<sup>6</sup></code></li>
	<li>All pairs <code>(x<sub>i</sub>, y<sub>i</sub>)</code> are distinct.</li>
</ul>

class Solution:
    class UF:
        def __init__(self, n):
            self


    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        parent = [i for i in range(n)]
        rank = [1] * n

        edges = []
        for i in range(n):
            for j in range(i+1, n):
                edges.append([abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]), (i,j)])

        # def find(x):
        #     if x != parent[x]:
        #         parent[x] = find(parent[x])
        #     return parent[x]
        
        def union(x,y):
            # nonlocal merges, cost
            par_x, par_y = find(x), find(y)

            if par_x == par_y:
                return False
            
            if rank[par_x] >= rank[par_y]:
                rank[par_x] = max(rank[par_x], 1 + rank[par_y])
                parent[par_y] = par_x
            else:
                parent[par_x] = par_y            
            return True

        def find(p):
            cur = parent[p]
            while cur != parent[cur]:
                cur = parent[cur]
            return cur

        # def union(i, j):
        #     pi, pj = find(i), find(j)

        #     if pi == pj:
        #         return False
        #     if rank[pi] > rank[pj]:
        #         parent[pj] = pi
        #         rank[pi] += rank[pj]
        #     else:
        #         parent[pi] = pj
        #         rank[pj] += rank[pi]
        #     return True

        merges = n - 1
        cost = 0
        heapify(edges)

        while merges:
            w, (x,y) = heappop(edges)
            if union(x,y):
                merges -= 1
                cost += w

        return cost
        

123434