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

# undirected graph

# Return the number of pairs of different nodes that are 
# at least 1 node, 10^5 node -> there can be a lot of nodess, big input
# lots of edge -> union find > dfs

# unreachable from each other.
# unreachable meaning can't dfs traverse it in one loop
# meaning not part of the same components
# -> union find?


# number of pairs of different nodes 
# 0,3 = 3,0 -> counts as one pair

# how to get total number of pairs knowing the amount of disjointed components we
# have

# arr = [1,2,4]
# count = 
# for i in range(len(arr)):
#     for j in range(i+1, len(arr)-1)
#         count += (arr[i]*arr[j])

# cycles don't matter in this case

# eliminate algo for DAG

class Solution:

    def countPairs(self, n: int, edges: List[List[int]]) -> int:
        



        # initialize for union-find
        rank = {}
        par = {}
        for i in range(n):
            rank[i] = 1
            par[i] = i
        

        # for par.values()
        # put them in a set
        # for each value in set, find their rank
        # that means in par - direct par is the one that we want to store        


        def union(n1, n2):
            # what i will call in countPairs
            # what do i need -> i need the size of each components
            # won't give it -> i ll need to look at par or rank
            
            p1, p2 = find(n1), find(n2)

            if p1 == p2:
                return 

            elif rank[p1] >= rank[p2]:
                par[p2] = p1
                rank[p1] += rank[p2]
            
            else:
                par[p1] = p2
                rank[p2] += rank[p1]


        def find(node):
            
            if node != par[node]:
                p = par[node]
                par[node] = find(p)
            
            return par[node]

        for n1, n2 in edges:
            union(n1,n2)
        
        components = {}


        for i in range(n):
            p_i = find(i)
            if p_i not in components:
                components[p_i] = rank[p_i]

        [4,2,1]
        []

        arr = list(components.values())
        if len(arr) == 1:
            return 0
        
        prefix_sum = arr[0]
        ans = 0

        for i in range(1,len(arr)):
            ans += (prefix_sum * arr[i])
            prefix_sum += (arr[i])
        
        print(arr)
        return ans

        

        
1747