0996MediumDepth-First SearchBreadth-First SearchUnion-FindGraph Theory

Recabling a Rack Until It Is One Network

Tracked in this browser only

Trains the technique from

LeetCode 1319Number of Operations to Make Network Connected

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def make_connected(n: int, cables: list[list[int]]) -> int:

Java

public int makeConnected(int n, int[][] cables)

The intended approach

Time O(n + m) near enough, for n machines and m cables, with the almost constant cost of the lookups.Space O(n) for the representatives and group sizes.

Tying `n` machines into one network takes at least one cable fewer than there are machines, and moving cables about never creates any, so with fewer than that the answer is `-1` whatever you do. Past that, count the separate groups the cables already leave. Keep a representative per group: start with every machine alone, and for each cable look up the representatives of its two ends, merging the groups when they differ and leaving things be when they match. Hanging the smaller group under the larger and flattening the chains while walking them keeps each lookup near constant. The answer is then one less than the group count. Each move can lift a cable that some group does not need and drop it between two groups, and such a cable always exists while more than one group is left: a group of so many machines needs only one cable fewer than that to hold together, so with at least one cable fewer than the machines in total, some group is carrying a spare. Since a move can only ever bring the group count down by one, one less than the count is both enough and unavoidable.

Pythonentry point: make_connected

def make_connected(n, cables):
    if len(cables) < n - 1:
        return -1
    parent = list(range(n))
    size = [1] * n
    def top(x):
        root = x
        while parent[root] != root:
            root = parent[root]
        while parent[x] != root:
            parent[x], x = root, parent[x]
        return root
    groups = n
    for pair in cables:
        a = top(pair[0])
        b = top(pair[1])
        if a == b:
            continue
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]
        groups -= 1
    return groups - 1

The obvious version

Check the cable count first, then build the neighbour lists and sweep the machines. Each machine not reached yet starts a fresh group, walked out with a stack that marks everything the cables lead to. The answer is one less than the groups counted. Leans on neighbour lists and a stack instead of representatives and sizes.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_make_connected(n, cables):
    if len(cables) < n - 1:
        return -1
    near = [[] for _ in range(n)]
    for pair in cables:
        near[pair[0]].append(pair[1])
        near[pair[1]].append(pair[0])
    seen = [False] * n
    groups = 0
    for start in range(n):
        if seen[start]:
            continue
        groups += 1
        seen[start] = True
        stack = [start]
        while stack:
            here = stack.pop()
            for there in near[here]:
                if not seen[there]:
                    seen[there] = True
                    stack.append(there)
    return groups - 1

How this problem was checked

Reference solution executed against 16 test cases — 16 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in