27. Critical Connections in a Network

hardAsked at CircleCI

Find all bridges in a network graph — edges whose removal disconnects the graph — mapping directly to CircleCI's infrastructure reliability analysis of single-point-of-failure links between build servers.

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

Problem

Given n servers and a list of connections, find all critical connections. A critical connection is one that, if removed, will make some servers unable to reach some other servers.

Constraints

2 <= n <= 10^5
n - 1 <= connections.length <= 10^5
0 <= ai, bi <= n - 1
ai != bi, no repeated connections

Examples

Example 1

Input

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

Output

[[1,3]]

Example 2

Input

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

Output

[[0,1]]

Approaches

1. Brute force edge removal

Remove each edge and run BFS/DFS to check connectivity; O(E * (V+E)) — too slow for large networks.

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

// Outline only — TLE on large inputs
// For each edge (u,v): remove it, BFS to check if all n nodes reachable
// If not: edge is critical
// Restore edge and continue

Tradeoff:

2. Tarjan's bridge-finding algorithm

Use DFS with discovery times and low-link values; an edge (u,v) is a bridge if low[v] > disc[u], meaning v cannot reach u or any ancestor of u without using the edge (u,v).

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

function criticalConnections(n, connections) {
  const graph = Array.from({length: n}, () => []);
  for (const [u, v] of connections) { graph[u].push(v); graph[v].push(u); }
  const disc = new Array(n).fill(-1);
  const low = new Array(n).fill(0);
  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]);
      }
    }
  }
  dfs(0, -1);
  return result;
}

Tradeoff:

CircleCI-specific tips

CircleCI expects you to know Tarjan's algorithm by name and explain low-link values intuitively — describe it as 'the earliest DFS timestamp reachable from a subtree via back edges' which signals whether a subtree can survive without an edge.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →