# 2316. Count Unreachable Pairs of Nodes in an Undirected Graph

2316. Count Unreachable Pairs of Nodes in an Undirected Graph
{%hackmd theme-dark %}
n = 5

[2, 3] [3, 1] [4,0]

{1, 2, 3} {0, 4}

3 * 2

return total number pair

{1, 2, 3} {0, 4} {5,6}
3*2*2 = 12

1. union find -> use graph to union vertices
2. multiple lenth of all group
n = 5
[2, 3] [3, 1] [4,0]
1. {1, 2, 3} {0, 4}
2. 3 * 2 = 6

edge:
[1,0] [0,1]

0:0 1:0

n = 7, [[0,2][0,5][2,4][1,6][5,4]]

{0, 2, 5, 4} {1, 6} {3}
4*1 + 4*2 + 2*1 = 14
14
[[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]]

class Solution(object):
    def countPairs(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: int
        """
        p = {x:x for x in range(n)}
        # {1:1, 2:2 ....}
        
        def find(x):
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]
        
        def union(x, y):
            xGroup = find(x)
            yGroup = find(y)
            
            if xGroup != yGroup:
                p[xGroup] = yGroup

        # do union find for edges
        for u, v in edges:
            union(u, v)
            
        # p: {1:1, 2:1, 3:1  0:0, 4:0}
        # new case
        # {0, 2, 5, 4} {1, 6} {3}
        group = deafultdict(int)
        # calculate groups
        for i in range(n):
            groupRoot = find(i)
            group[groupRoot] += 1
            
        #group -> {0:4, 1:2, 3:1}
        arr = list(group.values())
        # arr : [4, 2, 1]
        ans = 0
        for i in range(len(arr)-1):
            for j in range(i+1):
                ans += arr[i]*arr[j]
                # 4*2
                # 4*1
                # 2*1 
            
        return ans # 14

# N: number of Nodes
# E: number of edges
# TC: O(E)
# SC: O(N) -> hashmap p

###### tags: `mock interview` `面試`