Teaching Kids Programming – Count Unreachable Pairs of Nodes in an Undirected Graph (Recursive Depth 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 (Recursive Depth First Search Algorithm)

The number of edges equals to the sum of the degrees for all vertices in a Graph. For directed graphs, the degree for a vertex is the sum of both incoming and outgoing degrees.

The vertices/nodes in the same connected component form a same number of unreachable pairs of nodes. Then, the contribution of the vertex i is where c is the number of the vertices in the current component and n is the number of the vertex in the Graph.

Thus, we can use the Depth First Search Algorithm to count the number of components and the number of vertex in it.

The edges can be used to construct the Graph using the Adjacent List data structure. Then we need to go through the vertex and calculate the sum of contribution for the component once. The DFS is done via Recursion.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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 dfs(i):
            if i in seen:
                return 0
            seen.add(i)
            ans = 1
            for x in G[i]:
                ans += dfs(x)
            return ans
                
        for i in range(n):
            c = dfs(i)
            ans += c * (n - 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 dfs(i):
            if i in seen:
                return 0
            seen.add(i)
            ans = 1
            for x in G[i]:
                ans += dfs(x)
            return ans
                
        for i in range(n):
            c = dfs(i)
            ans += c * (n - c)
        return ans >> 1

We need to use a hash set to remember the nodes that we have visited in the DFS traversal. Each vertex is visited once so the time complexity is O(V+E). The space complexity is O(V+E) because we need to store the Undirected Graph using Adjacent List.

The following adds the contribution of each vertex separately aka (n – c). However, the time complexity is O(V^2) as for each vertex in the same component, the DFS has to be carried out to find out the number of vertices in the same component.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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

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

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