PreviousNext
Coding/Graphs and trees

Minimum cable replug operations

Write codeMedium30 min

Your task

There are n computers (0..n-1) connected by some bidirectional cables given as [a, b]. You may unplug any cable already in place and replug it between any two computers, including a pair not currently directly connected. Return the minimum number of such re-plug operations needed to make every computer connected to every other (one network). If it is impossible because there are not enough cables to span all computers, return -1. Duplicate cables and self-cables (a == b) may appear in the input.

Examples

min_reconnects(n: int, cables: list[list[int]]) -> int
Example 1
Inputmin_reconnects(4, [[0, 1], [0, 2], [1, 2]])
Output1