Teaching Kids Programming – Count Unreachable Pairs of Nodes in an Undirected Graph (Union Find and Disjoint Set Algorithm)

Teaching Kids Programming – Count Unreachable Pairs of Nodes in an Undirected Graph (Union Find and Disjoint Set Algorithm) | ninjasquad

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 $tex_045d83a396572ca8362170ebc697671b Teaching Kids Programming - Count Unreachable Pairs of Nodes in an Undirected Graph (Union Find and Disjoint Set Algorithm) algorithms data structure Disjoint Set Graph Algorithm python teaching kids programming Union Find youtube video$ 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.

GD Star Rating