Rebuild Rope Bridges to Join Every Island
Implement bridgesToMove
An archipelago has n islands joined by rope bridges, given as an adjacency list of an undirected graph. A move takes down one existing bridge and rebuilds it between any two islands. Find the smallest number of moves that lets people travel between every pair of islands, or -1 if there are not enough bridges.
Only two numbers matter: how many separate groups there are, and how many bridges are spare (they close a loop inside a group). Union-find counts both in one pass.
Example 1:
Input: network = [[1,2,3],[0,2,3],[0,1,3],[0,1,2],[5],[4],[]]
Output: 2
Example 2:
Input: network = [[1],[0],[],[]]
Output: -1
Example 3:
Input: network = [[]]
Output: 0
+ 15 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ n ≤ 10 islands numbered 0 … n-1; network[u] lists, in increasing order, every island joined to u by a bridge (adjacency-list form of an undirected graph) - ●
If v is in network[u] then u is in network[v]; there are no bridges from a island to itself and no repeated bridges - ●
One move takes down any existing bridge and rebuilds it somewhere else, so that it joins two islands of your choice - ●
Return the smallest number of moves needed so that every island can reach every other one, or -1 if that is impossible
network =
[[1,2,3], [0,2,3], [0,1,3], [0,1,2], [5], [4], []]