Module 2 · Connected Components

Count Unreachable Pairs of Nodes in an Undirected Graph

MediumProblem 8 of 25 9 min read ~25 min to solve LeetCode

GraphUnion FindDFSCombinatorics

Asked atAmazonGoogleMetaMicrosoftApple

Problem Statement

You are given an integer n representing nodes labelled 0..n-1 and an undirected edge list edges.

Return the number of unordered pairs of different nodes (a, b) such that there is no path between a and b. In other words, count how many node pairs belong to different connected components.

Input

An integer n and an undirected edge list edges.

Output

A long integer: the number of unordered pairs of nodes that cannot reach each other.

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.

Examples

Example 1

Input:

n = 3, edges = [[0,1],[0,2],[1,2]]

Output: 0

Explanation: All three nodes are in one component, so every pair is reachable.

Example 2

Input:

n = 7, edges = [[0,2],[0,5],[2,4],[1,6]]

Output: 14

Explanation: The component sizes are 4 for {0,2,4,5}, 2 for {1,6}, and 1 for {3}. Unreachable pairs are 4·2 + 4·1 + 2·1 = 14.

Learning Objectives

Move from counting components to using component sizes in a combinatorial formula.
Use Union-Find by size so every root knows how many nodes its component contains.
Avoid double-counting pairs by using a running total of nodes seen in previous components.
Use long for pair counts because n choose 2 can exceed 32-bit integer range.

Intuition

Once the graph is split into components, the edges inside a component no longer matter. A node can reach exactly the nodes in its own component and cannot reach any node outside it. So the entire problem reduces to: given component sizes, how many pairs choose nodes from two different sizes?

For a component of size s, there are s · (n - s) ordered-looking cross choices with nodes outside it, but if you sum that over every component, each unordered pair is counted twice: once from each side. That gives one correct formula: sum s · (n - s) / 2.

The cleaner interview trick is a running total. Process component sizes one by one. Suppose you have already seen seen nodes in earlier components. A new component of size s forms exactly s · seen unreachable pairs with those earlier nodes. Add that to the answer, then set seen += s. This counts every cross-component pair exactly once and never needs a division.

Union-Find by size is a natural fit because after all edges are unioned, each root already stores its component size. DFS component sizing also works, but Union-Find keeps the counting phase compact.

Common mistakes

×Using int for the answer; with 100,000 isolated nodes the answer is about 5 billion.
×Summing s · (n - s) and forgetting to divide by 2, which double-counts every pair.
×Reading component size from every node rather than only from roots, causing duplicate counts.
×Counting reachable pairs instead of unreachable pairs, or subtracting from total pairs with integer overflow.
×Trying to reason from the number of edges; only component sizes determine the answer.

Algorithm Explanation

Build a Union-Find with parent[i] = i and size[i] = 1.
Union every edge using union by size; when two roots merge, add the smaller component size into the larger root.
Iterate nodes 0..n-1. A node whose root is itself represents one completed component.
Let s be that root's component size. Add s · seen to the answer, where seen is the number of nodes in earlier components.
Increase seen by s and continue. Return the answer as a long.

Solutions

Solution: Union-Find by size plus running total

Union all reachable nodes into components while maintaining each root's size. Then process root sizes once, adding size · seen so each pair across two different components is counted exactly once.

Step-by-step

parent tracks the representative root for each node; size[root] tracks the number of nodes in that root's component.
For every edge, union its endpoints. If they are already in the same component, ignore the edge.
After all unions, scan nodes. Only roots should contribute a component size.
For each root size s, add s * seen to answer because every node in this component is unreachable from every node in all earlier components.
Add s to seen and continue until all roots are processed.

Time

O((n + E) · α(n))

Space

O(n)

Union-Find operations are effectively constant amortised time; arrays store parent and size.

Java implementation

Loading…

Dry Run

Sample input

n = 7, edges = [[0,2],[0,5],[2,4],[1,6]]. After unions, component sizes are 4 for {0,2,4,5}, 2 for {1,6}, and 1 for {3}.

Component	Size	seen before	Pairs added	Answer
{0,2,4,5}	4	0	4 * 0 = 0	0
{1,6}	2	4	2 * 4 = 8	8
{3}	1	6	1 * 6 = 6	14
done	7 nodes seen	-	return	14

The running-total method pairs each new component only with components already processed, so no unreachable pair is missed or counted twice. Final answer: 14.

Interview Tips

Do not stop at component counting; say explicitly that the real target is cross-component pairs. Derive the formula before coding: either sum s · (n - s) and divide by two, or use answer += s · seen. The running-total version sounds cleaner and avoids a final division. Also mention long early — it is a common hidden failure on this problem and a strong signal that you checked constraints.

Likely follow-ups

Return the number of reachable pairs instead, and derive it from component sizes.
Solve with DFS component sizes rather than Union-Find and compare memory trade-offs.
Edges are added one at a time; maintain the number of unreachable pairs after each addition.
Count unreachable ordered pairs instead of unordered pairs.

Key Takeaways

After components are known, only their sizes matter for unreachable pair counts.
answer += size * seen counts each cross-component pair exactly once.
Use long whenever pair counts can approach n choose 2.
Union-Find by size maintains component sizes during merges.

Reusable template: Component-size counting: find each connected component size, then aggregate cross-component pairs with answer += size * nodesSeenSoFar.