<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 {
public:
    struct point {
        int x , y ;
    };

    struct edge {
        int a , b , w ;
    }e;

    static bool cmp ( const edge x , const edge &y ) {
        return ( x.w < y.w ) ;
    }

    int par[1003] , sz[1003] ;
    map <int , point> mp ;
    vector <edge> v ;

    int fin ( int x ) {
        return par[x] = ( par[x] == x ? x : fin ( par[x] ) ) ;
    }

    void uni ( int x , int y ) {
        if ( ( x = fin( x ) ) == ( y = fin ( y ) ) ) return ;
        if ( sz[x] < sz[y] ) swap ( x , y ) ;
        par[y] = x ;
        sz[x] += sz[y] ;
    }

    int minCostConnectPoints(vector<vector<int>>& p) {
        int n = p.size() , l = 1 , sum = 0 ;
        for ( int i = 0 ; i <= 1001 ; i++ ) par[i] = i ;
        for ( auto it : p ) {
            mp[l].x = it[0] ;
            mp[l++].y = it[1] ;
        }
        for ( int i = 1 ; i <= n ; i++ ) {
            for ( int j = i+1 ; j <= n ; j++ ) {
                e.a = i ;
                e.b = j ;
                e.w = abs(mp[i].x-mp[j].x)+abs(mp[i].y-mp[j].y) ;
                v.push_back(e) ;
            }
        }
        sort ( v.begin() , v.end() , cmp ) ;
        n = v.size() ;
        for ( int i = 0 ; i < n ; i++ ) {
            if ( fin(v[i].a) != fin(v[i].b) ) {
                sum += v[i].w ;
                uni(v[i].a, v[i].b) ;
            }
        }
        return sum ;
    }
};
67075