Cables Whose Loss Splits the Network
Solve this ProblemA data centre has n servers joined by cables (an undirected graph given as an adjacency list). A cable is critical if removing it makes some servers unable to reach each other. Find all critical cables.
Trying every cable works but repeats a full search each time. Tarjan's algorithm finds all of them in a single depth-first search by comparing discovery times with the earliest time each subtree can reach ("low-link" values).
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ n ≤ 8 servers numbered 0 … n-1; graph[u] lists, in increasing order, every server joined to u by a cable (adjacency-list form of an undirected graph) - ◆
If v is in graph[u] then u is in graph[v]; there are no cables from a server to itself and no repeated cables - ◆
The network may consist of several separate parts - ◆
A cable is critical (a bridge) when removing it increases the number of separate parts. Return all critical cables as [u, v] with u < v, sorted by u and then by v
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Remove Each Cable and Count the Separate Parts
BruteCount the separate parts of the network. Then, for every cable, run a breadth-first search that pretends the cable is not there and count the parts again. If there are more parts than before, the cable was holding two parts together, so it is critical. Every cable needs its own full search.
O(E · (n + E))O(n)1class Solution {
2 private int countGroups(int[][] graph, int skipA, int skipB) {
3 int n = graph.length;
4 boolean[] seen = new boolean[n];
5 int groups = 0;
6 for (int start = 0; start < n; start++) {
7 if (seen[start]) continue;
8 groups++;
9 seen[start] = true;
10 Deque<Integer> queue = new ArrayDeque<>();
11 queue.add(start);
12 while (!queue.isEmpty()) {
13 int u = queue.poll();
14 for (int v : graph[u]) {
15 boolean skipped = (u == skipA && v == skipB) || (u == skipB && v == skipA);
16 if (!skipped && !seen[v]) {
17 seen[v] = true;
18 queue.add(v);
19 }
20 }
21 }
22 }
23 return groups;
24 }
25
26 public int[][] criticalLinks(int[][] graph) {
27 int base = countGroups(graph, -1, -1);
28 List<int[]> result = new ArrayList<>();
29 for (int u = 0; u < graph.length; u++) {
30 for (int v : graph[u]) {
31 if (u < v && countGroups(graph, u, v) > base) result.add(new int[]{u, v});
32 }
33 }
34 return result.toArray(new int[0][]);
35 }
36}Optimal — Tarjan’s Bridge-Finding DFS With Low-Link Values
OptimalRun one depth-first search and give every server a discovery time disc[]. Also keep low[u], the earliest discovery time that the subtree of u can reach: from u you may follow one cable back to an already discovered server v (low[u] = min(low[u], disc[v])), and after returning from a child v you take low[u] = min(low[u], low[v]). A tree cable (u, v) to a child v is critical exactly when low[v] > disc[u]: nothing in v's subtree connects back to u or above, so removing the cable cuts v's subtree off. The cable to the parent is skipped. One pass: O(n + E). Finally sort the answer.
O(n + E)O(n)1class Solution {
2 private int timer;
3
4 private void visit(int[][] graph, int u, int parent, int[] disc, int[] low, List<int[]> result) {
5 timer++;
6 disc[u] = timer;
7 low[u] = timer;
8 for (int v : graph[u]) {
9 if (v == parent) continue;
10 if (disc[v] != 0) {
11 low[u] = Math.min(low[u], disc[v]);
12 } else {
13 visit(graph, v, u, disc, low, result);
14 low[u] = Math.min(low[u], low[v]);
15 if (low[v] > disc[u]) result.add(new int[]{Math.min(u, v), Math.max(u, v)});
16 }
17 }
18 }
19
20 public int[][] criticalLinks(int[][] graph) {
21 int n = graph.length;
22 int[] disc = new int[n];
23 int[] low = new int[n];
24 List<int[]> result = new ArrayList<>();
25 timer = 0;
26 for (int start = 0; start < n; start++) {
27 if (disc[start] == 0) visit(graph, start, -1, disc, low, result);
28 }
29 result.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
30 return result.toArray(new int[0][]);
31 }
32}