<p>You are given an integer <code>n</code>. There is an <strong>undirected</strong> graph with <code>n</code> nodes, numbered from <code>0</code> to <code>n - 1</code>. You are given a 2D integer array <code>edges</code> where <code>edges[i] = [a<sub>i</sub>, b<sub>i</sub>]</code> denotes that there exists an <strong>undirected</strong> edge connecting nodes <code>a<sub>i</sub></code> and <code>b<sub>i</sub></code>.</p>

<p>Return <em>the <strong>number of pairs</strong> of different nodes that are <strong>unreachable</strong> from each other</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/05/05/tc-3.png" style="width: 267px; height: 169px;" />
<pre>
<strong>Input:</strong> n = 3, edges = [[0,1],[0,2],[1,2]]
<strong>Output:</strong> 0
<strong>Explanation:</strong> There are no pairs of nodes that are unreachable from each other. Therefore, we return 0.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/05/05/tc-2.png" style="width: 295px; height: 269px;" />
<pre>
<strong>Input:</strong> n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]
<strong>Output:</strong> 14
<strong>Explanation:</strong> There are 14 pairs of nodes that are unreachable from each other:
[[0,1],[0,3],[0,6],[1,2],[1,3],[1,4],[1,5],[2,3],[2,6],[3,4],[3,5],[3,6],[4,6],[5,6]].
Therefore, we return 14.
</pre>

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

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= edges.length &lt;= 2 * 10<sup>5</sup></code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt; n</code></li>
	<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>
	<li>There are no repeated edges.</li>
</ul>

class Solution {
public:
    long long countPairs(int n, vector<vector<int>>& edges) {
        
        map<int, vector<int>> m1;

        for(int i=0; i<edges.size(); i++)
        {
            int first = edges[i][0];
            int second = edges[i][1];

            m1[first].push_back(second);
            m1[second].push_back(first);
        }

        queue<int> q1;
        vector<int> vis(n,0);

        vector<int> sizes;

        int init = 0;

        for(int i=0; i<n; i++)
        {   
            init = 0;
            if(!vis[i] && m1.find(i)!=m1.end())
            {   
                init = 0;
                q1.push(i);
                
                vis[i] = 1;
                int next_loop = 1;
                while(!q1.empty())
                {   
                    int k =0;
                    int temp = next_loop;
                    next_loop=0;
                    while(k<temp)
                    {   

                        int front_ele = q1.front();
                        init++;
                        // cout<<"front_ele "<<front_ele<<"init is "<<init<<" ";
                        q1.pop();
                        k++;
                        vis[front_ele] = 1;
                        for(auto it: m1[front_ele])
                        {
                            if(!vis[it])
                            {
                                q1.push(it);
                                next_loop++;
                                vis[it] = 1;
                            }
                        }
                    }
                    
                } 
            }
            if(!vis[i] && m1.find(i) == m1.end())
            {
                init = 1;
            }
            sizes.push_back(init);
           

        }

        long long final = 0;

        if(sizes.size() <= 1) return 0;

        long long sum = sizes[0];
        for(int i=1; i<sizes.size(); i++)
        {
                final+=(sizes[i]*sum);
                sum+=sizes[i];
        }
        return final;
    }
};
196643