<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:
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size();
        unordered_map<int,vector<int>> adj;

        for(int i=0;i<points.size();i++)
        {
            for(int j=0;j<points.size();j++)
            {
                if(i!=j)
                {
                    adj[i].push_back(j);
                }
            }
        }

        // for(auto i : adj)
        // {
        //     cout<<i.first<<" ";
        //     for(int j=0;j<i.second.size();j++)
        //     {
        //         cout<<i.second[j]<<" ";
        //     }
        //     cout<<"\n";
        // }

        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> heap;
        set<int> v;

        int cost =0;

        heap.push({0,0}); // in the format {cost, node}

        
        while(v.size()!=n)
        {
            pair<int,int> node = heap.top();
            heap.pop();
            /*
            VVVImp. When we are pushing the adjacents of node to the heap.
            we check if the adj nodes are visited or not. We dp this to make sure
            that if one of the adjacent nodes is already visisted then it has already
            contributed to the cost of MST.

            But when we are popping the min cost from heap, that time also we need
            to check if the node with min cost that is popped has been visited or not.

            for example, first test case
            the point 3, is added to the heap as it is adj to the first node 0
            but it is not chosen as there was some other min. So it lies in the heap.
            Next for node 1, 3 comes again with a diff cost (cost of 1 and 3) and is added
            to the heap, as it is still not visited.
            But in case of 1, 3 is chosen and popped from the heap.
            but the first 3 that came in with 0 (with a cost of 0 and 3) is still there.
            So next time when min is chosen from the heap, it is possible
            the old 3 is chosen because the cost it had can be min.
            So every time before popping the min from the heap, we need to check if the
            min node is already visisted or not.
            */
            if(v.find(node.second)!=v.end())
            {
                continue;
            }
            
            v.insert(node.second);
            cout<<node.first<<" ";
            cost+=node.first;

            if(v.size()!=n)
            {
                for(int vertex : adj[node.second])
                {
                if(v.find(vertex)==v.end())
                {
                    int dist = abs(points[node.second][0]-points[vertex][0])+ abs(points[node.second][1]-points[vertex][1]);
                    heap.push({dist,vertex});
                }
                }
            }
            

        }

        return cost;
        
    }
};
95815