Count Unreachable Pairs of Nodes in an Undirected Graph

Count Unreachable Pairs of Nodes in an Undirected Graph

What is this problem about?

The Count Unreachable Pairs of Nodes in an Undirected Graph interview question asks you to find how many pairs of nodes (u, v) exist such that there is no path between them. You are given an undirected graph with n nodes and an edge list. Since "unreachable" means the nodes belong to different connected components, the problem effectively asks you to find all components and calculate the pairs formed between them.

Why is this asked in interviews?

Microsoft and Snapchat frequently ask this graph interview pattern to test knowledge of connectivity. It evaluates your ability to use traversal algorithms like BFS/DFS or Disjoint Set Union (DSU) to group nodes. It also tests your combinatorics skills—calculating pairs without using O(n^2) nested loops.

Algorithmic pattern used

The problem is solved in two steps:

1. Identify Components: Use DFS, BFS, or Union-Find to find the size of each connected component.
2. Combinatorial Counting: If component sizes are $s_1, s_2, ..., s_k$, the total unreachable pairs can be calculated using the formula: $\sum (s_i imes (n - s_i)) / 2$. Alternatively, keep a running total of nodes visited so far to avoid double-counting.

Example explanation

Suppose $n = 7$ and components are of size 3, 2, and 2.

• Component A (size 3) nodes cannot reach the other $7 - 3 = 4$ nodes. Pairs = $3 imes 4 = 12$.
• Component B (size 2) nodes cannot reach the $7 - 2 = 5$ other nodes. However, pairs with Component A were already counted.
• Efficient approach:
  • 1st component (3): total += 3 * (7-3) = 12. Remaining nodes = 4.
  • 2nd component (2): total += 2 * (4-2) = 8. Remaining nodes = 2.
  • 3rd component (2): total += 2 * (2-2) = 0. Result: 20.

Common mistakes candidates make

• Integer Overflow: The number of pairs can be as large as $n(n-1)/2$. For $n=10^5$, this exceeds 32-bit integer limits. Always use a 64-bit long for the sum.
• Double Counting: Forgetting to divide by 2 or failing to adjust the "remaining nodes" count in the summation logic.
• O(n^2) Pairs: Trying to explicitly check connectivity for every pair instead of using component sizes.

Interview preparation tip

Practice using Union-Find for connectivity problems. It's often easier to implement and can handle dynamic edge additions better than BFS/DFS, making it a favorite for interviewers.