2316 · Count Unreachable Pairs of Nodes

Given an integer n and undirected edges. Return the number of pairs (a, b) with a < b such that there is no path between them.

Simulation & Component Sizes

idle

INVARIANT Combinatorial Decomposition Invariant: A node in component of size s cannot reach any of the n - s nodes outside it. Maintain remaining = n. For each component size s: pairs += s * (remaining - s); remaining -= s. Time is O(V + E) rather than O(n²).

Formula: pairs = Σ s × (remaining - s)

Total Pairs:0

Remaining Nodes:7

Sizes:[]

Press Run to begin.

0 / 0

Java 21 Solution

INTERVIEW SCRIPT

How to Explain Count Unreachable Pairs to an Interviewer

1. The O(n²) Trap

"With $n = 10^5$, checking all $\binom{n}{2} \approx 5 \times 10^9$ pairs leads to immediate Time Limit Exceeded. We must solve this in $O(V + E)$ linear time."

2. Component Size Multiplication

"Any node in a connected component of size $s$ can reach exactly all $s$ nodes in that component. It cannot reach the other $n - s$ nodes outside it."

3. Avoid Double Counting

"Maintain remaining = n. For each component of size $s$, multiply pairs += (long) s * (remaining - s), then decrement remaining -= s. This counts every pair exactly once!"

4. 64-Bit Integer Overflow

"Total unreachable pairs can exceed $2 \times 10^9$, so the result must use a 64-bit long to prevent 32-bit integer overflow."