Rebuild Rope Bridges to Join Every Island
Solve this ProblemAn 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.
Test Case 1:
Test Case 2:
Test Case 3:
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
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Count the Groups by Spreading Labels
BruteConnecting n islands needs at least n − 1 bridges, so if there are fewer, the answer is -1. Otherwise count the separate groups of islands: give every island its own number as label and sweep repeatedly, letting each island take the smallest label among itself and its neighbours, until nothing changes. Each group ends up with one label, so the number of islands still carrying their own number equals the number of groups. Joining g groups needs g − 1 bridges, and there are always enough spare ones.
O(n · (n + E))O(n)1class Solution {
2 public int bridgesToMove(int[][] network) {
3 int n = network.length;
4 int bridges = 0;
5 for (int[] row : network) bridges += row.length;
6 bridges /= 2;
7 if (bridges < n - 1) return -1;
8 int[] label = new int[n];
9 for (int i = 0; i < n; i++) label[i] = i;
10 boolean changed = true;
11 while (changed) {
12 changed = false;
13 for (int u = 0; u < n; u++) {
14 for (int v : network[u]) {
15 if (label[v] < label[u]) {
16 label[u] = label[v];
17 changed = true;
18 }
19 }
20 }
21 }
22 int groups = 0;
23 for (int i = 0; i < n; i++) {
24 if (label[i] == i) groups++;
25 }
26 return groups - 1;
27 }
28}Optimal — Union-Find: Count Groups and Spare Bridges
OptimalGo through every bridge once with a union-find structure. If its two ends are already in the same group, the bridge is spare (it is not needed for connectivity); otherwise it merges two groups, so the number of groups drops by one. At the end there are g groups; connecting them needs g − 1 spare bridges that can be moved. So the answer is g − 1 if spare ≥ g − 1, and -1 otherwise.
O(n + E · α(n))O(n)1class Solution {
2 private int find(int[] parent, int x) {
3 while (parent[x] != x) {
4 parent[x] = parent[parent[x]];
5 x = parent[x];
6 }
7 return x;
8 }
9
10 public int bridgesToMove(int[][] network) {
11 int n = network.length;
12 int[] parent = new int[n];
13 for (int i = 0; i < n; i++) parent[i] = i;
14 int groups = n;
15 int spare = 0;
16 for (int u = 0; u < n; u++) {
17 for (int v : network[u]) {
18 if (u > v) continue;
19 int a = find(parent, u), b = find(parent, v);
20 if (a == b) {
21 spare++;
22 } else {
23 parent[a] = b;
24 groups--;
25 }
26 }
27 }
28 return spare >= groups - 1 ? groups - 1 : -1;
29 }
30}