Skip to main content

1192. Critical Connections in a Network

hardAsked at Amazon

Find all critical connections (bridges) in an undirected graph. Amazon asks this to test whether you know Tarjan's bridge-finding algorithm and can articulate the discovery-time / low-link invariant.

By Alex Chen, 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^5
  • n - 1 <= connections.length <= 10^5
  • 0 <= ai, bi <= n - 1
  • ai != bi
  • 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.

Approaches

1. 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.

Output

Press Run or Cmd+Enter to execute

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.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →