<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>

"""
Complexity Analysis

Time Complexity: O(n+e).
- For T operations, the amortized time complexity of the union-find algorithm (using path compression and union by rank) is O(a(T)), Here a(T) is the inverse Acker,ann function that grows so slowly that it doesn't exceed 4 for all reasonable T (approximately T < 10^600). 
- Because the function grows so slowly we consider it to be O(1)
- Initializing union find takes O(n), because we set of each node to its own parent.
- We iterate through every edge and perform union of the nodes connected by the edge which takes O(1) time per operation. It takes O(e) time for e edges.
We then iterate through all the nodes use the find operation O(1) to find their components size. There can be no more than N components because there are n nodes. In the worst-case scenario determining the size of each component is O(e)

Space complexity: O(n)
- We are using the parent and rank arrays, both of which require O(n) space each. 
- The component size map would require O(n) space
"""
class UnionFind:
    
    def __init__(self):
        self.parent = defaultdict(int)
        self.rank = defaultdict(int)
        self.count = 0
    
    def add_node(self, node):
        self.parent[node] = node
        self.rank[node] = 1
        self.count+=1
    
    def find(self, node):
        
        if self.parent[node]==node:
            return node
        
        # path compression
        self.parent[node] = self.find(self.parent[node])
        return self.parent[node]
    
    def union(self, node1, node2):
        
        parent1 = self.find(node1)
        parent2 = self.find(node2)
        
        if parent1==parent2:
            return
        
        if self.rank[parent1] > self.rank[parent2]:
            self.parent[parent2] = parent1
        elif self.rank[parent2] > self.rank[parent1]:
            self.parent[parent1] = parent2
        else:
            self.rank[parent1]+=1
            self.parent[parent2] = parent1
        
        self.count-=1
    
                
        
        
        

class Solution:
    def countPairs(self, n: int, edges: List[List[int]]) -> int:
    
        uf = UnionFind()
        unreachable_pairs = 0
        remaining_nodes = n
        
        for i in range(n):
            uf.add_node(i)
        
        for node1, node2 in edges:
            uf.union(node1, node2)
        
        # get the size of each component
        component_size = defaultdict(int)
        for node in range(n):
            component_size[uf.find(node)]+=1
        
        # go through each components size
        for size in component_size.values():
            remaining_nodes-=size #deduct the size of this component from the amount of total nodes
            # the combination of this components size and the size of the remaining nodes is the 
            # amount of unreachable nodes for this component
            unreachable_pairs += size * remaining_nodes
        
        return unreachable_pairs
            
        
        
        
        
        
1762