Count Unreachable Pairs of Nodes in an Undirected Graph - Video Solutions

Problem Overview: You are given n nodes and an edge list describing an undirected graph. Two nodes are considered unreachable if no path exists between them. The task is to count how many pairs of nodes belong to different connected components.

The key observation: nodes inside the same connected component can reach each other, so only nodes from different components contribute to the answer. Once you know the size of each component, you can count cross-component pairs efficiently.

Approach 1: Union-Find to Identify Components (Time: O(n + m * α(n)), Space: O(n))

This method uses the Disjoint Set Union structure to group nodes into connected components while processing edges. For every edge (u, v), perform a union operation so both nodes share the same root. After processing all edges, iterate through nodes and count how many belong to each root component. If component sizes are s1, s2, s3..., the number of unreachable pairs can be computed incrementally by multiplying each size with the remaining nodes not yet processed. Union-Find with path compression and union by rank keeps operations almost constant time. This approach works well when edges arrive dynamically or when you already use Union Find in your workflow.

Approach 2: Depth-First Search to Explore Components (Time: O(n + m), Space: O(n))

Build an adjacency list for the graph, then iterate through all nodes. If a node has not been visited, run a DFS to explore its entire connected component and count its size. Each DFS traversal returns the number of nodes reachable from that start node. Similar to the union-find solution, use component sizes to accumulate unreachable pairs by multiplying the current component size with the number of remaining nodes. DFS naturally fits graph traversal problems and is easy to implement using recursion or a stack. This approach relies on standard Depth-First Search traversal on an undirected graph.

BFS works identically if you prefer a queue-based traversal using Breadth-First Search. Both DFS and BFS discover connected components in linear time.

Recommended for interviews: Both DFS and Union-Find achieve optimal O(n + m)-style performance. DFS is often quicker to implement during interviews because it only requires an adjacency list and a visited array. Union-Find demonstrates stronger knowledge of disjoint-set data structures and is useful when the problem involves repeated connectivity queries. Showing either approach signals solid graph fundamentals.