Teaching Kids Programming – Count Unreachable Pairs of Nodes in an Undirected Graph (Breadth First Search Algorithm)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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.

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.

Constraints:
1 <= n <= 10^5
0 <= edges.length <= 2 * 10^5
edges[i].length == 2
0 <= ai, bi < n
ai != bi
There are no repeated edges.

Hints:
Find the connected components of the graph. To find connected components, you can use Union Find (Disjoint Sets), BFS, or DFS.
For a node u, the number of nodes that are unreachable from u is the number of nodes that are not in the same connected component as u.
The number of unreachable nodes from node u will be the same for the number of nodes that are unreachable from node v if nodes u and v belong to the same connected component.

Count Unreachable Pairs of Nodes in an Undirected Graph (Breadth First Search Algorithm)

Last time, we use the Depth First Search (DFS) algorithm to count the number of vertex in the undirected graph for each connected component Teaching Kids Programming – Count Unreachable Pairs of Nodes in an Undirected Graph (Recursive Depth First Search Algorithm). We can use the Breadth First Search (BFS) algorithm to achieve the same task:

And the number of all unreachable pairs is equal to the where c is the number of vertex in each connected component and n is the total number of vertices in the undirected graph.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution:
    def countPairs(self, n: int, edges: List[List[int]]) -> int:
        G = defaultdict(list)
        seen = set()
        for a, b in edges:
            G[a].append(b)
            G[b].append(a)
        ans = 0
        
        def bfs(i):
            if i in seen:
                return 0
            seen.add(i)
            q = deque([i])
            ans = 0
            while q:
                c = q.popleft()
                ans += 1
                for x in G[c]:
                    if x not in seen:
                        q.append(x)
                        seen.add(x)
            return ans
                            
        for i in range(n):
            c = bfs(i)
            ans += (n - c) * c
        return ans >> 1

class Solution:
    def countPairs(self, n: int, edges: List[List[int]]) -> int:
        G = defaultdict(list)
        seen = set()
        for a, b in edges:
            G[a].append(b)
            G[b].append(a)
        ans = 0
        
        def bfs(i):
            if i in seen:
                return 0
            seen.add(i)
            q = deque([i])
            ans = 0
            while q:
                c = q.popleft()
                ans += 1
                for x in G[c]:
                    if x not in seen:
                        q.append(x)
                        seen.add(x)
            return ans
                            
        for i in range(n):
            c = bfs(i)
            ans += (n - c) * c
        return ans >> 1

As we add the contribution for each component once in the undirected graph, each vertex will be visited exactly once, the time complexity is O(V+E), and the space complexity is O(V+E) as we are using a queue to implement the BFS algorithm and also we need to store the undirected Graph using Adjacent List.

Graph Algorithms to Count Unreachable Pairs of Nodes in an Undirected Graph

• Teaching Kids Programming – Count Unreachable Pairs of Nodes in an Undirected Graph (Recursive Depth First Search Algorithm)
• Teaching Kids Programming – Count Unreachable Pairs of Nodes in an Undirected Graph (Breadth First Search Algorithm)
• Teaching Kids Programming – Count Unreachable Pairs of Nodes in an Undirected Graph (Union Find and Disjoint Set Algorithm)

–EOF (The Ultimate Computing & Technology Blog) —