22. Critical Connections in a Network

mediumAsked at Palantir

Find all critical edges (bridges) in an undirected network whose removal disconnects it. Palantir asks this because their ontology team uses Tarjan's bridge algorithm to flag dependency edges in an ETL DAG whose removal would silo a downstream pipeline — bridges are blast-radius signals.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Source citations

Public interview reports confirming this problem appears in Palantir loops.

Glassdoor (2026-Q1)— Palantir FDE — explicitly named 'Tarjan's bridge algorithm' as the expected.
Blind (2025-11)— Tagged as Palantir 'graph blast radius' question.

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 server. 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: The triangle 0-1-2 keeps connectivity if any of its edges is removed, but removing [1,3] isolates server 3.

Example 2

Input

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

Output

[[0,1]]

Approaches

1. Brute force edge removal

For each edge, remove it and BFS to check if the graph is still connected.

Time: O(E * (V + E))
Space: O(V + E)

function criticalConnections(n, connections) {
  function isConnected(skipEdgeIdx) {
    const graph = Array.from({length: n}, () => []);
    for (let i = 0; i < connections.length; i++) {
      if (i === skipEdgeIdx) continue;
      const [a, b] = connections[i];
      graph[a].push(b); graph[b].push(a);
    }
    const visited = new Set([0]);
    const queue = [0];
    while (queue.length) {
      const u = queue.shift();
      for (const v of graph[u]) if (!visited.has(v)) { visited.add(v); queue.push(v); }
    }
    return visited.size === n;
  }
  const out = [];
  for (let i = 0; i < connections.length; i++) if (!isConnected(i)) out.push(connections[i]);
  return out;
}

Tradeoff: Trivial but O(E^2) — TLEs immediately at n=10^5. Palantir will reject this unless you also offer Tarjan's.

2. Tarjan's bridge-finding DFS

DFS with discovery time disc[u] and low-link low[u] = min discovery reachable from u's subtree via tree+back edges. 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 bridges = [];
  let time = 0;
  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: Linear time, single DFS — the canonical answer. Recursive though — for 10^5 nodes you may need to convert to an explicit stack to avoid overflow.

Palantir-specific tips

Palantir wants Tarjan's by name and the low-link invariant explicit before coding. State it clearly: 'low[u] is the earliest discovery time reachable from u's subtree, including via at most one back-edge.' Bonus signal: connect to ETL DAG blast radius — a bridge in the undirected dependency graph means breaking that edge silos a downstream consumer. They also love the iterative version (explicit stack) for production safety. Drop the algorithm name out loud — it's the senior signal here.

Common mistakes

Using parent equality but the graph has multiple edges between same pair — you'd skip a valid back edge. Track edge IDs instead of parent ID.
Updating low[u] = min(low[u], low[v]) for back edges — that's wrong; for back edges use disc[v], not low[v].
Forgetting that the recursive DFS will overflow on a chain of 10^5 nodes — convert to iterative for production submission.

Follow-up questions

An interviewer at Palantir may pivot to one of these next:

Articulation points (cut vertices) — same disc/low pattern, slightly different condition.
Strongly connected components — Tarjan's variant for directed graphs.
Online bridge maintenance — much harder, link-cut trees territory.

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 low[v] > disc[u] the bridge condition?

Because if v's subtree can reach a node discovered earlier than u (via any back edge), removing (u,v) doesn't disconnect — there's an alternate route. If low[v] > disc[u], no such alternate exists, so (u,v) is a bridge.

What's the difference between bridges and articulation points?

Bridges are edges whose removal disconnects the graph; articulation points are vertices whose removal disconnects. They're related but distinct — a graph can have many bridges and zero articulation points (e.g., a line graph).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →