Find the Cable That Closes the Loop
Solve this ProblemA company connected n computers with exactly n cables, one more than a tree needs, so the network has exactly one loop. You are given the cables in the order they were installed. Return the cable to remove so that all computers stay connected; if several cables work, return the one that appears last in the list.
Adding the cables one by one to a union-find structure reveals the answer: the cable whose ends are already connected when it arrives is the one that closes the loop.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
3 ≤ n ≤ 9 computers numbered 0 … n-1; links is a list of exactly n cables [u, v] (the graph as an edge list, in the order the cables were installed; the same graph is also the adjacency list built from these pairs) - ◆
The cables connect all n computers; a network of n computers connected by n − 1 cables would be a tree, so exactly one loop exists (no cable repeats and there are no cables from a computer to itself) - ◆
Removing any cable of the loop leaves a network that is still connected - ◆
Return the cable [u, v] to remove: if several cables can be removed, the one that appears LAST in links (returned in the same orientation as it appears)
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Try Removing Each Cable From the Last One Backwards
BruteThe cable to remove is the last one (in the list) whose removal leaves the network connected. So look at the cables from the last to the first: remove one, and run a breadth-first search from computer 0 to see whether every computer is still reached. The first cable for which this succeeds is the answer. Each attempt rebuilds the graph and searches it.
O(n · (n + n²)) with a matrixO(n²)1class Solution {
2 private boolean stillConnected(int[][] links, int skip) {
3 int n = links.length;
4 boolean[][] joined = new boolean[n][n];
5 for (int i = 0; i < n; i++) {
6 if (i == skip) continue;
7 joined[links[i][0]][links[i][1]] = true;
8 joined[links[i][1]][links[i][0]] = true;
9 }
10 boolean[] seen = new boolean[n];
11 Deque<Integer> queue = new ArrayDeque<>();
12 seen[0] = true;
13 queue.add(0);
14 int reached = 1;
15 while (!queue.isEmpty()) {
16 int u = queue.poll();
17 for (int v = 0; v < n; v++) {
18 if (joined[u][v] && !seen[v]) {
19 seen[v] = true;
20 reached++;
21 queue.add(v);
22 }
23 }
24 }
25 return reached == n;
26 }
27
28 public int[] extraLink(int[][] links) {
29 for (int i = links.length - 1; i >= 0; i--) {
30 if (stillConnected(links, i)) return new int[]{links[i][0], links[i][1]};
31 }
32 return new int[0];
33 }
34}Optimal — Union-Find: The First Cable Whose Ends Are Already Connected
OptimalAdd the cables one by one to a union-find structure that starts with every computer alone. A cable whose two ends are already in the same group would close a loop: with exactly one loop in the network there is exactly one such cable, and it is the LAST cable of the loop in the list, which is the required answer. Every other cable merges two groups. Each cable takes almost constant time.
O(n · α(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[] extraLink(int[][] links) {
11 int n = links.length;
12 int[] parent = new int[n];
13 for (int i = 0; i < n; i++) parent[i] = i;
14 for (int[] link : links) {
15 int a = find(parent, link[0]), b = find(parent, link[1]);
16 if (a == b) return new int[]{link[0], link[1]};
17 parent[a] = b;
18 }
19 return new int[0];
20 }
21}