DSA Tracker

Visualize

Count Unreachable Pairs of Nodes in an Undirected Graph

Size every connected component, then subtract reachable pairs from the total

time O(V + E)space O(V + E)

Two nodes are unreachable from each other exactly when they land in different connected components, so this never requires checking pairs directly. Find the size of every component with a BFS or DFS, then the count of REACHABLE pairs is just size*(size-1)/2 added up per component. Subtracting that sum from the total pairs among all n nodes, n*(n-1)/2, leaves exactly the unreachable pairs — one arithmetic pass after the components are known.

Details

Animated on: 7 nodes labeled 0..6 with undirected edges 0-2, 0-5, 2-4, 1-6, 5-4 — how many pairs of different nodes are unreachable from each other?

Problem:Count Unreachable Pairs of Nodes in an Undirected GraphMedium

Size every connected component, then subtract reachable pairs from the total

step 1 / 16

Undirected graph, n nodes

7 nodes and 5 undirected edges. A pair of nodes is unreachable exactly when they sit in different connected components, so the whole problem is: find the components, then count cross-component pairs.

Pseudocode
1FUNCTION countPairs(n, edges):
2  BUILD adjacency FROM edges
3  FOR EACH node FROM 0 TO n - 1
4    IF node NOT visited
5      size <- BFS(node, adjacency, visited)
6      APPEND size TO sizes
7  total <- n * (n - 1) / 2
8  reachable <- SUM(s * (s - 1) / 2 FOR s IN sizes)
9  RETURN total - reachable

← / → step · space play · Home restart

Every step in words

Show all 16 steps
  1. 7 nodes and 5 undirected edges. A pair of nodes is unreachable exactly when they sit in different connected components, so the whole problem is: find the components, then count cross-component pairs.
  2. Node 0 has not been visited yet, so it starts a fresh component. BFS from it will reach everything connected to it.
  3. Visit 0: neighbors 2 and 5 were unvisited, so they join the queue. Component so far: {0}.
  4. Visit 2: neighbor 4 was unvisited, so it joins the queue. Component so far: {0,2}.
  5. Visit 5: every neighbor is already visited, nothing new joins the queue. Component so far: {0,2,5}.
  6. Visit 4: every neighbor is already visited, nothing new joins the queue. Component so far: {0,2,5,4}.
  7. Component {0,2,5,4} is exhausted — size 4. All 4*3/2 = 6 pairs inside it are reachable from each other.
  8. Node 1 has not been visited yet, so it starts a fresh component (separate from {0,2,5,4}). BFS from it will reach everything connected to it.
  9. Visit 1: neighbor 6 was unvisited, so it joins the queue. Component so far: {1}.
  10. Visit 6: every neighbor is already visited, nothing new joins the queue. Component so far: {1,6}.
  11. Component {1,6} is exhausted — size 2. All 2*1/2 = 1 pairs inside it are reachable from each other.
  12. Node 3 has not been visited yet, so it starts a fresh component (separate from {0,2,5,4,1,6}). BFS from it will reach everything connected to it.
  13. Visit 3: every neighbor is already visited, nothing new joins the queue. Component so far: {3}.
  14. Component {3} is exhausted — size 1. All 1*0/2 = 0 pairs inside it are reachable from each other.
  15. Component sizes: [4, 2, 1]. Total pairs among 7 nodes is 7*6/2 = 21. Reachable pairs sum to 4*3/2 + 2*1/2 + 1*0/2 = 7.
  16. Unreachable pairs = total - reachable = 21 - 7 = 14. RETURN 14.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Count Unreachable Pairs of Nodes in an Undirected Graph in the editorAll Graph problemsBack to roadmap