hardGraphsPure DSA~30 min
Fewest Cable Moves to Connect Every Machine
Machines are linked by network cables. You may unplug any cable and replug it between two machines. Find the minimum number of moves to make the whole fleet connected, or report it is impossible.
Problem
There are n machines (0..n-1) and a list connections where connections[i] = [a, b] is a cable between a and b. You may remove any cable and place it between any two disconnected machines. Return the minimum number of moves to connect all machines, or -1 if it cannot be done.
Input
An integer n and a connections list of [a, b] cables.
Output
An integer: the minimum moves, or -1.
Constraints
- 1 <= n <= 10^5
- 1 <= connections.length <= min(n*(n-1)/2, 10^5)
- No duplicate cables or self-loops.
Examples
Example 1
Input
n = 4, connections = [[0,1],[0,2],[1,2]]
Output
1
Three cables among {0,1,2}; move one redundant cable to reach 3.
Example 2
Input
n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
Output
2
Two spare cables connect the remaining two isolated machines.