1192. Critical Connections in a Network
hardAsked at DoorDashGiven an undirected graph, return all bridges — the edges whose removal disconnects the graph. DoorDash candidates report interviewers want Tarjan's bridge-finding algorithm by name, because a logistics network is exactly the kind of system where a single point of failure between zones matters; the question grades whether you can explain discovery times and low-link values, not whether you memorized the code.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in DoorDash loops.
- Glassdoor (2026-Q1)— DoorDash SWE onsite reports cite Critical Connections as a hard graph question on infra rounds.
- Blind (2025-12)— DoorDash SDE2 reports note Tarjan's as the algorithm DoorDash interviewers want by name.
Problem
There are n servers numbered from 0 to n - 1 connected by undirected server-to-server connections forming a network where connections[i] = [a_i, b_i] represents a connection between servers a_i and b_i. 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 server. Return all critical connections in the network in any order.
Constraints
2 <= n <= 10^5n - 1 <= connections.length <= 10^50 <= a_i, b_i <= n - 1a_i != b_iThere are no repeated connections.
Examples
Example 1
n = 4, connections = [[0,1],[1,2],[2,0],[1,3]][[1,3]]Explanation: [[3,1]] is also accepted.
Example 2
n = 2, connections = [[0,1]][[0,1]]Explanation: With only one edge connecting the two servers, that edge is trivially a bridge — removing it isolates them.
Approaches
1. Tarjan's bridge-finding DFS
DFS tracking discovery time (disc) and the earliest discovery reachable through subtree (low). An edge (u, v) is a bridge if 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);
let time = 0;
const bridges = [];
function dfs(u, parent) {
disc[u] = low[u] = time++;
for (const v of graph[u]) {
if (disc[v] === -1) {
dfs(v, u);
low[u] = Math.min(low[u], low[v]);
if (low[v] > disc[u]) bridges.push([u, v]);
} else if (v !== parent) {
low[u] = Math.min(low[u], disc[v]);
}
}
}
for (let i = 0; i < n; i++) {
if (disc[i] === -1) dfs(i, -1);
}
return bridges;
}Tradeoff: DoorDash's expected answer. Tarjan's is the canonical algorithm. The disc/low arrays + the bridge condition low[v] > disc[u] are the textbook formulation.
2. Edge removal + connectivity check (anti-pattern)
For each edge, remove it and run BFS/DFS to check if the graph stays connected.
- Time
- O(E * (V + E))
- Space
- O(V + E)
function criticalConnectionsBrute(n, connections) {
function isConnected(skip) {
const adj = Array.from({ length: n }, () => []);
for (let i = 0; i < connections.length; i++) {
if (i === skip) continue;
const [a, b] = connections[i];
adj[a].push(b);
adj[b].push(a);
}
const visited = new Set([0]);
const stack = [0];
while (stack.length) {
const u = stack.pop();
for (const v of adj[u]) if (!visited.has(v)) { visited.add(v); stack.push(v); }
}
return visited.size === n;
}
const bridges = [];
for (let i = 0; i < connections.length; i++) {
if (!isConnected(i)) bridges.push(connections[i]);
}
return bridges;
}Tradeoff: O(E * (V+E)) — fails the constraint at n = 10^5. Mention as the obvious approach, then derive Tarjan's. Bloomberg interviewers explicitly grade whether you reach Tarjan's by name.
DoorDash-specific tips
DoorDash interviewers want you to name TARJAN'S aloud. State: 'this is the bridge-finding problem — Tarjan's algorithm in O(V+E) using discovery and low-link times.' Don't apologize if you have to think through the disc/low details — interviewers expect that.
Common mistakes
- Treating the graph as directed — connections are undirected.
- Forgetting the parent check in the back-edge case (you'd treat the parent edge as a back-edge).
- Using disc[v] instead of low[v] in the bridge condition — that misses certain bridges.
Follow-up questions
An interviewer at DoorDash may pivot to one of these next:
- Articulation Points (LC 1568, conceptually) — Tarjan's variant for cut vertices.
- Number of Provinces (LC 547) — simpler connectivity counting.
- Redundant Connection II (LC 685) — find the redundant edge.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why low[v] > disc[u], not >=?
If low[v] == disc[u], v can reach u (or an ancestor) via another path — so removing (u, v) doesn't disconnect. Strict greater-than is required.
What's the parent-check pitfall?
In the back-edge clause, we skip the immediate parent because the tree edge (u, parent) is not a back-edge. Without this check, low gets corrupted.
Couldn't I just remove each edge and test connectivity?
That works but costs O(E) connectivity checks at O(V + E) each — O(E * (V + E)) total, hopeless at 10^5 edges. Tarjan's finds every bridge in one O(V + E) DFS, which is why interviewers ask for it by name.
Free learning resources
Curated free links for this problem.