n computers numbered 0 to n − 1. The list cables describes the cables already laid: a pair [a, b] is a cable between computers a and b. Two computers can talk if there is a path of cables between them, either direct or through other computers.
In one move you may unplug any existing cable and run it between any two computers that are not yet directly connected.
Return the fewest moves after which every computer can reach every other one. If that cannot be done, return -1.n=5, cables=[[0, 1], [1, 2], [2, 0], [3, 4]] → 1
Computers 0, 1 and 2 form a triangle, so one of its cables is spare. Moving it to join, say, 2 and 3 connects the whole network in one move.
n=5, cables=[[0, 1], [1, 2], [3, 4]] → -1
Connecting 5 computers takes at least 4 cables, and there are only 3.
n=3, cables=[[0, 2], [2, 1]] → 0
n=5, cables=[[0, 1], [1, 2], [2, 0], [3, 4]]
1
Run checks the first 3 tests in your browser. Submit checks all 88 tests on the server, hidden ones included.