Show problems as
Classic problem #1319MediumDepth-First SearchBreadth-First SearchUnion-FindGraph Theory

Number of Operations to Make Network Connected

Real-world version: Recabling a Rack Until It Is One Network
Tracked in this browser only
Read Number of Operations to Make Network Connected on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A rack holds n machines numbered 0 through n - 1. Each entry cables[i] = [a, b] is a cable running directly between machine a and machine b.

In one move you may unplug a cable at both ends and plug it back in between any two machines you choose.

Two machines can talk when some run of cables leads from one to the other. Return the fewest moves that leave every machine able to talk to every other, or -1 when no number of moves can manage it.

Examples

Example 1

Input
n = 5, cables = [[0, 1], [1, 2], [0, 2], [3, 4]]
Output
1

Machines 0, 1 and 2 are cabled in a ring, so one of their three cables is spare. Machines 3 and 4 form a second group. Moving the spare cable to run between the two groups joins the whole rack in one move.

Example 2

Input
n = 7, cables = [[0, 1], [2, 3], [4, 5]]
Output
-1

Seven machines need at least six cables to hold together and only three are on the rack, so no amount of replugging can do it.

Example 3

Input
n = 4, cables = [[0, 1], [1, 2], [2, 3]]
Output
0

The cables already run through every machine in one line, so nothing needs moving.

Constraints

  • 1 <= n <= 10^5
  • 1 <= cables.length <= 10^5
  • cables[i].length == 2
  • 0 <= cables[i][j] <= n - 1
  • The two ends of a cable are different machines.
  • No pair of machines is cabled twice.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def make_connected(n: int, cables: list[list[int]]) -> int:
Java
public int makeConnected(int n, int[][] cables)

More on the same topics