You are given an integer n. There is an undirected graph with n nodes, numbered from 0 to n - 1. You are given a 2D integer array edges where edges[i] = [ai, bi] denotes that there exists an undirected edge connecting nodes ai and bi.

Return the number of pairs of different nodes that are unreachable from each other.

&nbsp;
Example 1:

Input: n = 3, edges = [[0,1],[0,2],[1,2]]
Output: 0
Explanation: There are no pairs of nodes that are unreachable from each other. Therefore, we return 0.


Example 2:

Input: n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]
Output: 14
Explanation: 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.


&nbsp;
Constraints:


	1 &lt;= n &lt;= 105
	0 &lt;= edges.length &lt;= 2 * 105
	edges[i].length == 2
	0 &lt;= ai, bi &lt; n
	ai != bi
	There are no repeated edges.


'''
* Make groups of nodes which are connected
    eg., edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]

    0 ---- 2 1 --- 6 3
    | |
    | |
    5 ---- 4

    groups will be {0: 4, 1: 2, 3: 1},
    i.e 4 nodes are present in group0, 2 nodes are present in group1 and 1 node is present in group3

* Now, we have [4, 2, 1] as no of nodes in each group, we have to multiply each of no. with remaining
    ans = (4 * 2 + 4 * 1) + (2 * 1)
    but calculating ans this way will give TLE.

* if we notice, (4 * 2 + 4 * 1) + (2 * 1), we can combine, equation like this,
    4 * 2 + (4 + 2) * 1, using this, we can reduce complexity.
    so, if we have count of groups array as [a, b, c, d], ans will be,
    ans = a * b + (a + b) * c + (a + b + c) * d

* will use, union for generating groups.
* ps, you can modify UnionFind class as per your need. Have implemented full union-find for beginners.
'''

class UnionFind:
    def __init__(self, size):
        self.root = [i for i in range(size)]
        self.rank = [1] * size
    def find(self, x):
        if x == self.root[x]:
            return x
        self.root[x] = self.find(self.root[x])
        return self.root[x]
    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            if self.rank[rootX] > self.rank[rootY]:
                self.root[rootY] = rootX
            elif self.rank[rootX] < self.rank[rootY]:
                self.root[rootX] = rootY
            else:
                self.root[rootY] = rootX
                self.rank[rootX] += 1

class Solution:
    def countPairs(self, n: int, edges: List[List[int]]) -> int:
        dsu = UnionFind(n)
        for u, v in edges:
            dsu.union(u, v)
        C = Counter([dsu.find(i) for i in range(n)])
        groupCounts = list(C.values())
        ans = 0
        firstGroupCount = groupCounts[0]
        for i in range(1, len(groupCounts)):
            ans += firstGroupCount * groupCounts[i]
            firstGroupCount += groupCounts[i]
        return ans
class Solution {
  public long countPairs(int n, int[][] edges) {
    //Building Graph
    ArrayList < ArrayList < Integer >> graph = new ArrayList < > ();
    for (int i = 0; i < n; i++) graph.add(new ArrayList < Integer > ());
    for (int arr[]: edges) {
      graph.get(arr[0]).add(arr[1]);
      graph.get(arr[1]).add(arr[0]);
    }
    boolean visited[] = new boolean[n];
    long res = 0;
    int prev = 0;
    int count[] = {
      0
    };
    for (int i = 0; i < graph.size(); i++) { // Running for loop on all connected components of graph
      if (visited[i] == true) continue; // if the node is alredy reached by any of other vertex then we don't need to terverse it again
      dfs(graph, i, visited, count);
      long a = n - count[0]; // (total - current count)
      long b = count[0] - prev; // (current count - prev )
      prev = count[0]; // Now Store count to prev
      res += (a * b);
    }
    return res;
  }
  void dfs(ArrayList < ArrayList < Integer >> graph, int v, boolean vis[], int count[]) {
    vis[v] = true;
    count[0]++; //for counting connected nodes
    for (int child: graph.get(v)) {
      if (!vis[child]) {
        dfs(graph, child, vis, count);
      }
    }
  }
}
class Solution {
public:
    typedef long long ll;
    void dfs(int node, unordered_map<int,vector<int>>& m, ll& cnt, vector<int>& vis){
        vis[node] = 1;
        cnt++;
        for(auto& i: m[node]){
            if(vis[i]==0) dfs(i,m,cnt,vis);   
        }
    }
    long long countPairs(int n, vector<vector<int>>& edges) {
        unordered_map<int,vector<int>> m; // making adjacency list
        for(int i=0;i<edges.size();i++){
            m[edges[i][0]].push_back(edges[i][1]);
            m[edges[i][1]].push_back(edges[i][0]);
        }
        ll ans = ((ll)n*(n-1))/2;
        vector<int> vis(n,0);
        for(int i=0;i<n;i++){
            if(vis[i]==0){ // as node is not visited, we find the no. of nodes in current component.
                ll cnt = 0;
                dfs(i,m,cnt,vis);
                ans -= (cnt*(cnt-1))/2;
            }
        }
        return ans;
    }
};
var countPairs = function(n, edges) {
    const adj = [];

    for (let i = 0; i < n; i++) {
        adj.push([]);
    }
    
    for (let [from, to] of edges) {
        adj[from].push(to);
        adj[to].push(from);
    }
    
    const visited = new Set();

    function dfs(from) {
        visited.add(from);

        let count = 1;

        for (const to of adj[from]) {
            if (!visited.has(to)) {
                count += dfs(to);
            }
        }
        
        return count;
    }

    const groups = [];
        
    for (let i = 0; i < n; i++) {
        if (!visited.has(i)) {
            const count = dfs(i);
            groups.push(count);
        }
    }
    
    let ans = 0;
    
    for (let i = 0; i < groups.length - 1; i++) {
        for (let j = i + 1; j < groups.length; j++) {
            ans += groups[i] * groups[j];
        }
    }
    
    return ans;
};
Count Unreachable Pairs of Nodes in an Undirected Graph