Critical Connections in a Network Hard 0 attempts
LeetCode ↗

Critical Connections in a Network

Hard GraphBFSDFS LeetCode

Given n servers and connections between them, find all critical connections (bridges) whose removal would disconnect some servers.

Example: n=4, connections=[[0,1],[1,2],[2,0],[1,3]] → Output: [[1,3]]

Sample Input
—
Sample Output
—
Constraints
  • 2 <= n <= 10^5
  • n - 1 <= connections.length <= 10^5
Test Cases
Case 1
Args: [4,[[0,1],[1,2],[2,0],[1,3]]] Expected: [[1,3]]
Topics
GraphBFSDFS

Tarjan's Bridge Algorithm

Track discovery time and lowest reachable ancestor for each node.

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 = Array(n).fill(-1), low = Array(n).fill(0), 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;
}

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

Saved in this browser only. Private to you.

JavaScript