Cut-Off Pairs
MediumGraphs
Problem
After a storm, a utility company has n substations numbered 0 to n - 1, and edges lists the two-way lines still working.
Return the number of unordered pairs of distinct substations {x, y} that can no longer reach each other through working lines.
Example 1
- Input:
- n = 6, edges = [[0,1],[1,2],[3,4]]
- Output:
- 11
The groups have sizes 3, 2 and 1. Cross-group pairs: 3·2 + 3·1 + 2·1 = 11.
Example 2
- Input:
- n = 3, edges = [[0,1],[0,2],[1,2]]
- Output:
- 0
Constraints
- 1 ≤ n ≤ 10^5
- 0 ≤ edges.length ≤ 2 · 10^5
- 0 ≤ a, b < n
Hint
Show the first hint
Two substations are cut off exactly when they lie in different connected components.
Walkthrough
How to approach it
01Clarify before coding
- Are pairs unordered? Yes, {x, y} and {y, x} are the same pair.
- How large can the answer be? Up to n(n-1)/2 ≈ 5 · 10^9, which overflows 32-bit integers; use 64-bit (JavaScript numbers are exact up to 2^53).
- Are lines two-way? Yes.
02Brute force
Label components, then compare the labels of every pair of substations.
Cost: O(n²) pairs: 5 · 10^9 comparisons at n = 10^5.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.