There are n computers (0 .. n-1) connected by network cables. You can unplug any
existing cable and replug it elsewhere. Return the minimum number of cables to move to
connect every computer into one network, or -1 if it's impossible (too few cables).
extraCable(n, cables)
Connecting n computers needs at least n-1 cables; if there are fewer, it's
impossible. Otherwise the answer is (number of connected components) - 1.
Input format: n | cables, cables as a,b pairs.
n=4, cables (0,1)(1,2)(0,2) // → 1 (extra cable in {0,1,2} connects 3)
n=6, cables (0,1)(0,2)(0,3)(1,2)(1,3) // → 2
n=3, cables (0,1) // → -1 (1 cable, need 2)
First, the hard limit: connecting n computers into one network needs at least n-1 cables in a tree arrangement. Fewer than that, and no rearrangement can reach everyone — immediately -1.
With at least n-1 cables, the question becomes: how many existing cables are wasted on redundant connections within already-connected clusters? A cable connecting two computers already reachable via another path does no new connectivity work — it's redundant, and can be unplugged and moved without disconnecting anything.
Union-find handles this directly: process every cable as a union of its endpoints. A union that actually merges two groups means that cable did real work. A union whose endpoints are already in the same group means that cable is redundant — free to move. After processing all cables, the remaining distinct groups tell you how fragmented the network is.
With c separate clusters, you need c-1 new connections to link them all — one bridge per merge, one fewer bridge than clusters. Whenever there are at least n-1 total cables, there are guaranteed to be at least c-1 redundant ones to repurpose: c components covering n nodes need at least n-c cables just to stay internally connected, so with n-1 cables total, at least (n-1)-(n-c) = c-1 must be redundant — exactly enough for every needed bridge.
def extra_cable(n, cables):
if len(cables) < n - 1:
return -1
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
components = n
for a, b in cables:
ra, rb = find(a), find(b)
if ra != rb:
parent[ra] = rb
components -= 1
return components - 1
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.