Critical Connections in a Network
Find every connection whose removal disconnects the network, the bridges of the graph, with one DFS that tracks discovery times and low-link values (Tarjan's algorithm).
Problem Understanding
Critical Connections in a Network (LeetCode 1192): n servers are joined by undirected connections and every server can reach every other. A connection is critical if removing it leaves some server unable to reach another. Return all critical connections in any order.
Examples: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]] → [[1,3]]; n = 2, connections = [[0,1]] → [[0,1]].
The Intuition: Can the Subtree Climb Back?
An edge is critical exactly when it is not on any cycle. One DFS finds that for every edge at once:
- Stamp each server with the time the DFS first reaches it.
- Track how high each subtree can climb: the earliest stamp it reaches through one back edge (
low). - Test each tree edge u–v when v returns: if v's subtree cannot climb to u or above (
low[v] > disc[u]), the edge is a bridge.
The DFS itself is the one from Introduction to DFS. If a cycle is all you need, Redundant Connection finds the edge that closes one with union-find.
Interactive Walkthrough
ABOVE A SERVER: disc/low · RED = BRIDGE · AMBER = BACK EDGE
DFS FROM 0
at
:
low
:
bridges
0
7 servers, 8 connections. Start a DFS from server 0
Next
Visit 0: disc = low = 0
connections
n
Each visited server shows disc/low above it. Amber edges are back edges that let a subtree climb; red edges are bridges. Try Ring (no bridges) and Star (all bridges).
Dry Run Table
Input: n = 7, connections 0-1, 1-2, 2-0, 1-3, 3-4, 4-5, 5-3, 5-6. DFS order 0, 1, 2, 3, 4, 5, 6 (disc 0 to 6).
| Event | low update | Edge verdict |
|---|---|---|
| 2–0 back edge | low[2] = 0 | |
| 2 returns to 1 | low[1] = 0 | 1–2 kept (0 ≤ 1) |
| 5–3 back edge | low[5] = 3 | |
| 6 returns to 5 | low[6] = 6 | 5–6 bridge (6 > 5) |
| 5 returns to 4 | low[4] = 3 | 4–5 kept |
| 4 returns to 3 | low[3] = 3 | 3–4 kept |
| 3 returns to 1 | low[3] = 3 | 1–3 bridge (3 > 1) |
| 1 returns to 0 | low[0] = 0 | 0–1 kept |
Answer: [[5,6],[1,3]].
The Solution Template
Tarjan's bridge-finding DFS.
Critical Connections in a Network Code
1var criticalConnections = function(n, connections) {2 const graph = Array.from({ length: n }, () => []);3 for (const [a, b] of connections) {4 graph[a].push(b);5 graph[b].push(a);6 }7 const disc = new Array(n).fill(-1);8 const low = new Array(n).fill(0);9 const bridges = [];10 let time = 0;11 const dfs = (u, parent) => {12 disc[u] = low[u] = time++;13 for (const v of graph[u]) {14 if (v === parent) continue;15 if (disc[v] === -1) {16 dfs(v, u);17 low[u] = Math.min(low[u], low[v]);18 if (low[v] > disc[u]) bridges.push([u, v]);19 } else {20 low[u] = Math.min(low[u], disc[v]);21 }22 }23 };24 dfs(0, -1);25 return bridges;26};
Edge Cases & Common Mistakes
- Not skipping the parent: the tree edge looks like a back edge and no bridge is ever found.
- Using low[v] instead of disc[v] on a back edge: gives the right bridges here but is wrong for articulation points; disc[v] is the standard form.
- ≥ instead of >: low[v] = disc[u] means v's subtree reaches u by another path, so u–v is on a cycle.
- Removing each edge and re-checking connectivity: correct but O(E · (V + E)).
- Deep recursion: raise the recursion limit or use an explicit stack for long chains.
Summary
DFS once, stamping disc and computing low from children and back edges; a tree edge u–v is critical when low[v] > disc[u]. O(V + E) time and space.
More practice: DSA interview questions with answers · patterns cheat sheet