Rewire to Connect Everyone
MediumGraphs
Problem
An office has n machines numbered 0 to n - 1 and a set of cables, each [a, b] joining two machines. A technician may move a cable: unplug both ends and plug it between any two machines.
Return the minimum number of moves needed so that every machine can reach every other one, or -1 if it cannot be done with the cables available.
Example 1
- Input:
- n = 4, cables = [[0, 1], [0, 2], [1, 2]]
- Output:
- 1
One of the three cables in the 0–1–2 triangle is spare; move it to reach machine 3.
Example 2
- Input:
- n = 6, cables = [[0, 1], [0, 2], [0, 3], [1, 2]]
- Output:
- -1
Connecting 6 machines needs at least 5 cables.
Example 3
- Input:
- n = 6, cables = [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3]]
- Output:
- 2
Three groups ({0, 1, 2, 3}, {4}, {5}) need two joins, and there are two spare cables.
Constraints
- 1 ≤ n ≤ 10^5
- 0 ≤ cables.length ≤ 10^5
- 0 ≤ a, b < n, a ≠ b
Hint
Show the first hint
How many cables does a connected network of n machines need at minimum?
Walkthrough
How to approach it
01Clarify before coding
- Does a move have to keep the cable's old ends? No, both ends can be replugged anywhere.
- Can machines already be connected? Yes, then the answer is 0.
- Are duplicate cables possible? Yes; a duplicate is simply a spare cable.
02Brute force
Search over sequences of moves with BFS on network states until everything is connected.
Cost: Exponential in the number of cables; unusable.
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.