Repatching the rig

A theatre's dimmer racks are patched together with control cables, but not all of them are talking. You may unplug a cable and plug it in anywhere else.

The problem

There are racks dimmer racks, numbered 0 to racks - 1. Each cable [a, b] joins two racks and carries control data both ways. Racks connected directly or through other racks form one cluster.

In one move you unplug a cable from its two racks and plug it into any other pair. Find the smallest number of moves that leaves every rack in a single cluster, or return -1 when no sequence of moves can do it.

There is at most one cable between a pair of racks, and no cable joins a rack to itself.

Input. racks — an integer. cables — a list of [a, b] pairs.

Output. The smallest number of moves, or -1.

Example.

racks = 4, cables = [[0,1], [0,2], [1,2]]  ->  1

Racks 0, 1 and 2 form a triangle, rack 3 is stranded. The triangle has one cable more than it needs, so unplug [1,2] and run it to rack 3. One move.

Example.

racks = 6, cables = [[0,1], [0,2], [0,3], [1,2]]  ->  -1

Four cables. Six racks need at least five cables to sit on one chain, and moving a cable never creates a new one, so the answer is -1 no matter how the four are arranged.

Constraints.

• 1 <= racks <= 10^5
• 0 <= len(cables) <= 10^5
• 0 <= a, b < racks and a != b
• No pair of racks appears twice.

Hints

Approach

Brute force

Search over which cable to move and where to plug it. With 10⁵ cables and 10¹⁰ possible destinations per move, even one level of that search is out of reach, and the moves compound.

The insight

The count of moves never depends on which cables you move: joining c clusters takes exactly c - 1 moves, and the only question left is whether the rig holds racks - 1 cables at all.

Each move can merge at most two clusters, so c - 1 is a floor. It is also reachable: if len(cables) >= racks - 1, then any rig with more than one cluster has a cluster carrying more cables than racks minus one, so some cable inside it lies on a loop and can be pulled without splitting anything. Under racks - 1 cables no arrangement connects everything, which is the -1 case and the only one.

Algorithm

1. If len(cables) < racks - 1, return -1 immediately.
2. Put every rack in its own set.
3. For each cable, union its two racks; each union that joins two different sets drops the cluster count by one.
4. Return clusters - 1.

Complexity

Time O(V + E·α) — one near-constant union per cable. Space O(V) for the parent array.

Solution

"""Repatching the rig — count the clusters, then check there are enough spare cables."""


def cluster_count(racks, cables):
    """Number of connected clusters, via union-find with path compression."""
    parent = list(range(racks))

    def root(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]   # halve the path on the way up
            x = parent[x]
        return x

    clusters = racks
    for a, b in cables:
        ra, rb = root(a), root(b)
        if ra != rb:                        # invariant: a merge always drops the count by one
            parent[ra] = rb
            clusters -= 1
    return clusters


def solve(racks, cables):
    if len(cables) < racks - 1:             # a chain of n racks needs n-1 cables, full stop
        return -1
    return cluster_count(racks, cables) - 1

TESTS = [
    # Three racks in a triangle, one rack stranded: one spare cable, one move.
    ((4, [[0, 1], [0, 2], [1, 2]]), 1),
    # Four racks over-patched, two stranded: two moves.
    ((6, [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3]]), 2),
    # Four cables cannot join six racks however they are moved.
    ((6, [[0, 1], [0, 2], [0, 3], [1, 2]]), -1),
    # Already one chain: nothing to do.
    ((5, [[0, 1], [1, 2], [2, 3], [3, 4]]), 0),
    # A single rack is already connected to itself.
    ((1, []), 0),
    # Two separate loops plus one loose rack: two moves.
    ((7, [[0, 1], [1, 2], [2, 0], [3, 4], [4, 5], [5, 3]]), 2),
]

Pitfalls

• Testing len(cables) < racks. The off-by-one rejects a rig that is already one chain: five racks on four cables is connected and needs no moves.
• Counting spare cables per cluster. It is extra bookkeeping that changes no answer — the single global count already decides the -1 case.
• Forgetting racks = 1. Zero cables, one cluster, zero moves; a check written as len(cables) < racks - 1 handles it, one written with <= 0 bounds does not.

Variants

• Two cabinets — the same components, but the question is about a colouring inside each one rather than a count.
• Union-find — the structure that makes the cluster count one pass over the cables.