Teaching Kids Programming – Count Unreachable Pairs of Nodes in an Undirected Graph (Union Find and Disjoint Set 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 (Union Find and Disjoint Set Algorithm)

A Disjoint (Non-overlapping) Set is a data structure that provides near constant operations of Adding New Set, Merge Two Sets, and Checking if an element in a Set. However, we have to compress the paths when we find a parent/root of an element otherwise in the worst case the operation will be O(N) linear. We can use Disjoint Set to perform the Union Find Algorithm on an undirected Graph.

The disjoint set is initialized with N groups (N is the number of the vertex in the undirected graph), then we merge vertex A and B if there is an edge between them. Then we can find out easily the number of vertex/elements in the group where vertex i is in. And like other approaches (DFS or BFS), we need to sum up the where c is the number of elements in each connected component and n is the total number of vertex in the undirected graph.

1
2
3
4
5
6
7
8
9
10

class Solution:
    def countPairs(self, n: int, edges: List[List[int]]) -> int:
        ans = 0
        UF = UnionFind(n)
        for a, b in edges:
            UF.unite(a, b)
        for i in range(n):
            c = UF.getsize(i) 
            ans += c * (n - c)
        return ans >> 1

class Solution:
    def countPairs(self, n: int, edges: List[List[int]]) -> int:
        ans = 0
        UF = UnionFind(n)
        for a, b in edges:
            UF.unite(a, b)
        for i in range(n):
            c = UF.getsize(i) 
            ans += c * (n - c)
        return ans >> 1

The merge or union method can be iterative or recursive – see below the Union Find / Disjoint Set implementation in Python:

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42

class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.size = [1] * n
        self.setCount = n
    
    def findset(self, x: int) -> int:
        root = x
        while root != self.parent[root]:
            root = self.parent[root]
        while x != root:
            p = self.parent[x]
            # compress the path
            self.parent[x] = root
            x = p
        return root
        # the following is the recursive version
        if x != self.parent[x]:
            self.parent[x] = self.findset(self.parent[x])
        return self.parent[x]
    
    def unite(self, x: int, y: int) -> bool:
        x, y = self.findset(x), self.findset(y)
        if x == y:
            return False
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.parent[y] = x
        self.size[x] += self.size[y]
        self.size[y] = 0
        self.setCount -= 1
        return True
    
    def getsize(self, x) -> int:
        return self.size[x]
    
    def sz(self) -> int:
        return self.setCount
    
    def connected(self, x: int, y: int) -> bool:
        x, y = self.findset(x), self.findset(y)
        return x == y

class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.size = [1] * n
        self.setCount = n
    
    def findset(self, x: int) -> int:
        root = x
        while root != self.parent[root]:
            root = self.parent[root]
        while x != root:
            p = self.parent[x]
            # compress the path
            self.parent[x] = root
            x = p
        return root
        # the following is the recursive version
        if x != self.parent[x]:
            self.parent[x] = self.findset(self.parent[x])
        return self.parent[x]
    
    def unite(self, x: int, y: int) -> bool:
        x, y = self.findset(x), self.findset(y)
        if x == y:
            return False
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.parent[y] = x
        self.size[x] += self.size[y]
        self.size[y] = 0
        self.setCount -= 1
        return True
    
    def getsize(self, x) -> int:
        return self.size[x]
    
    def sz(self) -> int:
        return self.setCount
    
    def connected(self, x: int, y: int) -> bool:
        x, y = self.findset(x), self.findset(y)
        return x == y

To compress paths for intermediate nodes, we minimize the costs of finding roots. We prefer merging/attaching the group of a smaller size to a bigger one.

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