Count Unreachable Pairs of Nodes in an Undirected Graph Solution
Count Unreachable Pairs of Nodes in an Undirected Graph solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Count Unreachable Pairs of Nodes in an Undirected Graph is a medium coding problem on depth-first search, breadth-first search and graph, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Breadth-First Search, Graph, Union Find
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given n nodes labelled 0 through n - 1 and a list of undirected edges.
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
Example 2
Input: n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]
Output: 14
Example 3
Input: n = 4, edges = []
Output: 6
Constraints
1 <= n <= 600 <= edges.length <= 90There are no duplicate edges and no self-loops.The answer fits in a signed 32-bit integer.
Hints for Count Unreachable Pairs of Nodes in an Undirected Graph
Hint 1
Two nodes are reachable exactly when they sit in the same connected component.
Hint 2
So find the component sizes — union-find or a flood fill both work.
Hint 3
Every pair drawn from two different components is unreachable; accumulate
size * (nodes counted so far)as you sweep the components.
How to solve Count Unreachable Pairs of Nodes in an Undirected Graph
Nodes are mutually reachable iff they share a component, so find component sizes and count cross-component pairs.
Approach
- Union-find with sizes.
- Sweep roots: add
size · seenSoFarand then addsizetoseenSoFar.
Why it works
Every pair drawn from two different components is unreachable, and the running-sum sweep counts each such pair exactly once.
Complexity
- Time —
O((n + e) · α(n)) - Space —
O(n)
Pitfalls
- The count can exceed 32 bits — use a wide integer.
Reference solution
Python
def countPairs(n: int, edges) -> int:
parent = list(range(n))
size = [1] * n
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for a, b in edges:
ra, rb = find(a), find(b)
if ra != rb:
parent[ra] = rb
size[rb] += size[ra]
unreachable = 0
seen_so_far = 0
for i in range(n):
if find(i) != i:
continue
unreachable += size[i] * seen_so_far
seen_so_far += size[i]
return unreachableJava
private static int findRoot(int[] parent, int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
public static int countPairs(int n, int[][] edges) {
int[] parent = new int[n];
int[] size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
for (int[] e : edges) {
int a = findRoot(parent, e[0]);
int b = findRoot(parent, e[1]);
if (a != b) {
parent[a] = b;
size[b] += size[a];
}
}
int unreachable = 0, seenSoFar = 0;
for (int i = 0; i < n; i++) {
if (findRoot(parent, i) != i) continue;
unreachable += size[i] * seenSoFar;
seenSoFar += size[i];
}
return unreachable;
}C++
static int findRoot(vector<int>& parent, int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
int countPairs(int n, vector<vector<int>>& edges) {
vector<int> parent(n), size(n, 1);
for (int i = 0; i < n; i++) parent[i] = i;
for (const auto& e : edges) {
int a = findRoot(parent, e[0]);
int b = findRoot(parent, e[1]);
if (a != b) {
parent[a] = b;
size[b] += size[a];
}
}
int unreachable = 0, seenSoFar = 0;
for (int i = 0; i < n; i++) {
if (findRoot(parent, i) != i) continue;
unreachable += size[i] * seenSoFar;
seenSoFar += size[i];
}
return unreachable;
}JavaScript
var countPairs = function(n, edges) {
const parent = [], size = [];
for (let i = 0; i < n; i++) {
parent.push(i);
size.push(1);
}
const find = function(x) {
while (parent[x] !== x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
};
for (let i = 0; i < edges.length; i++) {
const a = find(edges[i][0]);
const b = find(edges[i][1]);
if (a !== b) {
parent[a] = b;
size[b] += size[a];
}
}
let unreachable = 0, seenSoFar = 0;
for (let i = 0; i < n; i++) {
if (find(i) !== i) continue;
unreachable += size[i] * seenSoFar;
seenSoFar += size[i];
}
return unreachable;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)