#1192
Critical Connections in a Network
Hard Tarjan's bridges
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
In an undirected connected network, return every connection whose removal disconnects some servers (the bridges).
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: edges whose removal cuts the network.
Why this works: Tarjan: low[v] is the earliest node v's subtree can reach with a back edge. If low[v] > disc[u], the edge u-v is the only way back.
Example: 0-1, 1-2, 2-0, 1-3
triangle 0-1-2 has back edges1-3: low[3] = 3 > disc[1] → bridge [1,3]
✦Hints open one at a time
DFS gives each node a discovery time.
low[u] = the earliest discovery time reachable from u's subtree using at most one back edge.
Edge (u, v) to a child v is a bridge when low[v] > disc[u].
↗Approach
Tarjan's algorithm: DFS with a timer. For each child v, recurse and set low[u] = min(low[u], low[v]); for a visited non-parent neighbour, low[u] = min(low[u], disc[v]). Record (u, v) if low[v] > disc[u].
</>Solution (Java)
import java.util.*;
class Solution {
private List<List<Integer>> adj;
private int[] disc, low;
private int timer = 1;
private final List<List<Integer>> bridges = new ArrayList<>();
public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (List<Integer> c : connections) {
adj.get(c.get(0)).add(c.get(1));
adj.get(c.get(1)).add(c.get(0));
}
disc = new int[n]; // 0 = not visited
low = new int[n];
dfs(0, -1);
return bridges;
}
private void dfs(int u, int parent) {
disc[u] = low[u] = timer++;
for (int v : adj.get(u)) {
if (v == parent) continue; // don't use the edge we came from
if (disc[v] == 0) {
dfs(v, u);
low[u] = Math.min(low[u], low[v]);
if (low[v] > disc[u]) bridges.add(Arrays.asList(u, v)); // v can't reach above u
} else {
low[u] = Math.min(low[u], disc[v]);
}
}
}
}!Common mistake
Updating low through the parent edge, which hides every bridge.
Complexity
- Time: O(V + E).
- Space: O(V + E).
Topic: Graphs
🎬 Episodes 74–85: video coming soon