<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:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        parent = [0] * (len(points)+1)
        size = [0] *  (len(points)+1)
        n = len(points)
        
        # Utility function to find set of an
        # element v using path compression
        # technique
        def find_set(v):
            
        #if v is parent
            if (v == parent[v]):
                return v
        
            # Otherwise, recursively
            # find its parent
            parent[v] = find_set(parent[v])
        
            return parent[v]
        
        # Function to perform union
        # of the sets a and b
        def union_sets(a, b):
            
            # Find parent of a and b
            a = find_set(a)
            b = find_set(b)
        
            # If parent are different
            if (a != b):
                
                # Swap Operation
                if (size[a] < size[b]):
                    a, b = b, a
        
                # Update parent of b as a
                parent[b] = a
                size[a] += size[b]
                return 1
        
            # Otherwise, return 0
            return 0
 

        # Stores adjacency list of graph
        v = []
    
        # Traverse each coordinate
        for i in range(n):
            for j in range(i + 1, n):
    
                # Find the Manhattan distance
                p = abs(points[i][0] -
                        points[j][0])
    
                p += abs(points[i][1] -
                        points[j][1])
    
                # Add the edges
                v.append([p, i, j])
    
        # Sort all the edges
        v = sorted(v)
    
        # Initialize parent[] and size[]
        for i in range(n):
            parent[i] = i
            size[i] = 1
    
        # Stores the minimum cost
        ans = 0
    
        # Finding the minimum cost
        for x in v:
    
            # Perform the union operation
            if (union_sets(x[1], x[2])):
                ans += x[0]
        return ans
        
    

            
103324