Skip to main content

1192. Critical Connections in a Network

hardAsked at DoorDash

Given an undirected graph, return all bridges — edges whose removal disconnects the graph. DoorDash uses Tarjan's bridge-finding algorithm because logistics networks need to identify single points of failure in their routing infrastructure.

By Alex Chen, 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^5
  • n - 1 <= connections.length <= 10^5
  • 0 <= a_i, b_i <= n - 1
  • a_i != b_i
  • There are no repeated connections.

Examples

Example 1

Input
n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output
[[1,3]]

Explanation: [[3,1]] is also accepted.

Example 2

Input
n = 2, connections = [[0,1]]
Output
[[0,1]]

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.

Output

Press Run or Cmd+Enter to execute

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.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Critical Connections in a Network and other DoorDash interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →