1192. Critical Connections in a Network
hardAsked at AmazonFind all critical connections — the bridges of an undirected graph, edges whose removal splits the network. Amazon candidates report this hard as a Tarjan's litmus test: at 10^5 nodes and edges the brute-force remove-and-recheck approach is hopeless, so the interview comes down to whether you can articulate the discovery-time / low-link invariant out loud rather than recite memorized code.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Amazon loops.
- Glassdoor (2026-Q1)— Amazon SDE II/III onsite reports cite this as the bridge-finding graph hard.
- Blind (2025-10)— Recurring Amazon interview problem for L5+ roles.
Problem
There are n servers numbered from 0 to n - 1 connected by undirected server-to-server connections forming a network where connections[i] = [ai, bi] represents a connection between servers ai and bi. Any server can reach other servers directly or indirectly through the network. A critical connection is a connection that, if removed, will make some servers unable to reach some other servers. Return all critical connections in the network in any order.
Constraints
2 <= n <= 10^5n - 1 <= connections.length <= 10^50 <= ai, bi <= n - 1ai != biThere are no repeated connections.
Examples
Example 1
n = 4, connections = [[0,1],[1,2],[2,0],[1,3]][[1,3]]Explanation: Servers 0, 1, 2 form a cycle, so removing any one of those edges leaves an alternate path — only the spur edge to server 3 is a bridge. [[3,1]] is also accepted.
Example 2
n = 2, connections = [[0,1]][[0,1]]Explanation: A two-node network with a single link has no redundancy at all — that one edge is trivially critical.
Approaches
1. Brute force: remove each edge, test connectivity
For every edge, delete it, run a BFS/DFS from node 0, and check whether all n nodes are still reachable. If not, the edge is a bridge.
- Time
- O(E * (V + E))
- Space
- O(V + E)
function criticalConnections(n, connections) {
const bridges = [];
for (let skip = 0; skip < connections.length; skip++) {
const graph = Array.from({ length: n }, () => []);
for (let e = 0; e < connections.length; e++) {
if (e === skip) continue;
const [a, b] = connections[e];
graph[a].push(b);
graph[b].push(a);
}
const seen = new Array(n).fill(false);
const stack = [0];
seen[0] = true;
let count = 1;
while (stack.length) {
const u = stack.pop();
for (const v of graph[u]) if (!seen[v]) { seen[v] = true; count++; stack.push(v); }
}
if (count < n) bridges.push(connections[skip]);
}
return bridges;
}Tradeoff: Conceptually obvious and worth one sentence to frame the problem, but at 10^5 edges it is 10^5 full graph traversals — far beyond any time limit. Its only interview value is motivating why a single-pass algorithm must exist.
2. Tarjan's bridge-finding (optimal)
DFS the graph. Track disc[u] = discovery time, low[u] = lowest disc reachable from u's subtree. An edge (u, v) is a bridge iff low[v] > disc[u].
- Time
- O(V + E)
- Space
- O(V + E)
function criticalConnections(n, connections) {
const graph = Array.from({ length: n }, () => []);
for (const [a, b] of connections) {
graph[a].push(b);
graph[b].push(a);
}
const disc = new Array(n).fill(-1);
const low = new Array(n).fill(-1);
const result = [];
let timer = 0;
function dfs(u, parent) {
disc[u] = low[u] = timer++;
for (const v of graph[u]) {
if (v === parent) continue;
if (disc[v] === -1) {
dfs(v, u);
low[u] = Math.min(low[u], low[v]);
if (low[v] > disc[u]) result.push([u, v]);
} else {
low[u] = Math.min(low[u], disc[v]);
}
}
}
for (let i = 0; i < n; i++) if (disc[i] === -1) dfs(i, -1);
return result;
}Tradeoff: Tarjan's runs in linear time. The invariant — low[v] > disc[u] means v's subtree has no back-edge above u, so removing (u,v) disconnects v's subtree — is the bridge condition.
Amazon-specific tips
Amazon interviewers grade this on whether you can articulate Tarjan's invariant. State out loud: 'disc[u] is the time we first saw u. low[u] is the earliest disc we can reach by going through u\'s subtree + at most one back-edge. An edge (u, v) is a bridge iff v\'s subtree can\'t reach above u — that is, low[v] > disc[u].' If you can't articulate that invariant, the code looks like memorized magic.
Common mistakes
- Confusing parent edge with back-edge — visiting the parent in an undirected graph is NOT a back-edge.
- Using a single parent variable when the graph can have multi-edges (here it can't — connections are unique — but defensive coding helps).
- Updating low[u] using disc[v] for tree edges (should use low[v]) and using low[v] for back-edges (should use disc[v]).
Follow-up questions
An interviewer at Amazon may pivot to one of these next:
- Articulation points (LC 1568 variant) — slightly different condition.
- Strongly Connected Components via Tarjan's SCC algorithm.
- What if the graph were directed?
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why is the bridge condition low[v] > disc[u]?
If low[v] > disc[u], no descendant of v can reach u or above via any back-edge. So removing the edge (u, v) isolates v's subtree. That's the definition of a bridge.
Is Tarjan's expected for a 45-minute interview?
Yes — this problem name itself signals 'bridge-finding,' and Amazon interviewers expect Tarjan's. Memorize the invariant + the disc/low update rules.
Will recursive DFS blow the stack at n = 10^5?
It can — a path-shaped graph produces recursion 10^5 deep, which overflows default stacks in most runtimes. Mentioning the iterative-DFS (explicit stack) rewrite, or at least naming the risk, is a senior-level signal on this problem.