<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 UnionFind{
public:
    UnionFind(int n ){
        parent.resize(n);
        rank.resize(n);
        for(int i =0;i<n;i++){
            parent[i] = i;
            rank[i] = 0;
        }
        numComponents = n;
    }

    int Find(int node){
        int root = parent[node];
        while(root != parent[root])
            root = parent[root];
        
        int cur = node;
        while(cur != parent[cur]){
            int next = parent[cur];
            parent[cur] = root;
            cur = next;
        }
        return root;
    }

    bool Union(int x, int y){
        int rootx = Find(x);
        int rooty = Find(y);

        if(rootx == rooty) return true;

        if(rank[rootx] < rank[rooty]) parent[rootx] = rooty;
        else if( rank[rootx] > rank[rooty]) parent[rooty] = rootx;
        else{
            parent[rooty] = rootx;
            rank[rootx] += 1;
    
        }
        numComponents--;
        return false;
    }

    int getNumComponents(){ return numComponents; }
    private:
    vector<int> parent;
    vector<int> rank;
    int numComponents;
};

class Compare{

public :
    bool operator()(const vector<int>& a, const vector<int>& b){
        return a[2] < b[2];
    }
};

typedef priority_queue<vector<int>, vector<vector<int>>, Compare> PQ;

class Solution {
public:
    int manhatanDistance(vector<int>& x, vector<int>& y){
        return abs(x[0]-y[0]) + abs(x[1] - y[1]);
    }

    void addEdges(vector<bool>& visited, PQ & pq, vector<vector<int>>& points, int& start){
        visited[start] = true;

        for(int i =0 ;i<points.size();i++){
            if(visited[i] || start == i )
                continue;
            pq.push({start,i,manhatanDistance(points[start],points[i])});
        }
    }
    // void relaxEdges(vector<bool>& visited,multiset<vector<int>, decltype([](const vector<int> & a, const vector<int> & b){ 
    //     return a[2] < b[2];
    //     })>& mtset, unordered_map<int, multiset<vector<int>, decltype([](const vector<int> & a, const vector<int> & b){ return a[2] < b[2];
    //     })>::iterator>& map, vector<vector<int>>& points, int& start){
    //     visited[start] = true;

    //     for(int i =0;i<points.size();i++){
    //         if(visited[i] || start == i)
    //             continue;
    //         int mhDis = manhatanDistance(points[start],points[i]);
    //         if(map.find(i) != map.end()){
    //             if(mhDis > (*(map[i]))[2])
    //                 continue;
    //             mtset.erase(map[i]);
    //         } 
    //         map[i] = mtset.insert({start,i,mhDis});
    //     }
    // }
    
    int minCostConnectPoints(vector<vector<int>>& points) {
        // Kruskal Algorithm ...
        // UnionFind uf(points.size());
        // vector<vector<int>> edgeList;
        // for(int i =0;i<points.size();i++){
        //     for(int j = i+1;j<points.size();j++)
        //     {
        //         edgeList.push_back({i,j,manhatanDistance(points[i],points[j])});
        //     }
        // }
        // sort(edgeList.begin(),edgeList.end(),[&](auto& x, auto& y){
        //     return x[2] < y[2];
        // });
        // int ans = 0;
        // for(auto& x: edgeList){
        //     if(!uf.Union(x[0],x[1]))
        //         ans += x[2];
        //     if(uf.getNumComponents() == 1)
        //         return ans;
        // }
        // return ans;

        // Prim's Algorithm ...
        int n = points.size();
        // vector<vector<pair<int,int>>> adjList(n);
        // for(int i =0;i<points.size();i++){
        //     for(int j = i+1;j<points.size();j++)
        //     {
        //         adjList[i].push_back({j,manhatanDistance(points[i],points[j])});
        //         adjList[j].push_back({i,manhatanDistance(points[i],points[j])});
        //     }
        // }
        vector<bool> visited(n, false);
        // Define a custom comparator lambda function 
    auto customComparator 
        = [](const vector<int>& a, const vector<int>& b) { return a[2] < b[2]; }; 
  
    // Create a multiset with the custom comparator 
    multiset<vector<int>, decltype(customComparator)> mtset( 
        customComparator); 
        //priority_queue<vector<int>, vector<vector<int>>, Compare> pq;

        //multiset<vector<int>> mtlset;
        // multiset<vector<int>, decltype([&](const vector<int> & a, const vector<int> & b){ return a[2] < b[2];})> mtset([&](const vector<int> & a, const vector<int> & b){ return a[2] < b[2];})>;
        unordered_map<int, multiset<vector<int>, decltype(customComparator)>::iterator > map;
        //vector<vector<int>> mstEdge(n);
        int mstEdgeCount =0 ;
        int mstCost = 0;
        int start = 0;
        //addEdges(visited,pq,points,start);
        //relaxEdges(visited,mtset, map,points,start);
        visited[start] = true;

        for(int i =0;i<points.size();i++){
            if(visited[i] || start == i)
                continue;
            int mhDis = manhatanDistance(points[start],points[i]);
            if(map.find(i) != map.end()){
                //std::cout<<i<<std::endl;
                if(mhDis > ((*map[i])[2]))
                    continue;
                mtset.erase(map[i]);
            } 
            map[i] = mtset.insert({start,i,mhDis});
        }

        while(!mtset.empty() && mstEdgeCount < n){
            auto cur = mtset.begin();
            auto temp = *cur;
            mtset.erase(cur);
            if(map.find(temp[1]) != map.end()){
                map.erase(temp[1]);
            }
            //std::cout<<temp[0]<<"\t"<<temp[1]<<"\t"<<temp[2]<<std::endl;
            if(visited[temp[1]]) continue;
            
            //mstEdge[mstEdgeCount] = cur;
            mstEdgeCount++;
            mstCost += temp[2];

            //addEdges(visited,pq,points,cur[1]);
            //relaxEdges(visited,mtset, map,points,temp[1]);
           visited[temp[1]] = true;

            for(int i =0;i<points.size();i++){
                if(visited[i] || temp[1] == i)
                    continue;
                int mhDis = manhatanDistance(points[temp[1]],points[i]);
                if(map.find(i) != map.end()){
                    // std::cout<<i<<std::endl;
                    // for(auto x : (*map[i]))
                    //     std::cout<<x<<"\t";
                    //std::cout<<std::endl;
                    if(mhDis > ((*map[i])[2]))
                        continue;
                    mtset.erase(map[i]);
                } 
                map[i] = mtset.insert({temp[1],i,mhDis});
            }

        }
        // for(auto& x: mstEdge){
        //     for(auto& y :x )
        //         std::cout<<y<<"\t";
        //     std::cout<<std::endl;
        // }
        if(mstEdgeCount != n-1)
            return 0;
        return mstCost;


    }
};
43125