Critical Connections in a Network Hard 0 attempts
LeetCode ↗

Critical Connections in a Network

Hard GraphBFSDFS LeetCode

You're given n servers and a list of direct connections between them. Identify every critical connection — a bridge edge that, if removed, would split the network and leave some servers unable to reach others.

Input Format
Implement criticalConnections(n, connections). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement. The order of the outer result array does not matter. Order inside each group does not matter either.

Sample Input and Output

Example 1 · Run Sample

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]]
Constraints
  • 2 <= n <= 10^5
  • n - 1 <= connections.length <= 10^5
  • The network is connected and undirected, with no self-loops or duplicate edges.
Test Cases (2)
Case 1
Args: [4,[[0,1],[1,2],[2,0],[1,3]]] Expected: [[1,3]]
Case 2
Args: [2,[[0,1]]] Expected: [[0,1]]
Topics
GraphBFSDFS

Iterative Tarjan Bridge Search

Record discovery times and the earliest ancestor reachable from each subtree. When returning from a child, its edge is a bridge if its low-link value is greater than the parent’s discovery time. Explicit frames support long chains.

javascript
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),parent=Array(n).fill(-1),result=[];let time=0;
  for(let start=0;start<n;start++)if(disc[start]===-1){
    disc[start]=low[start]=time++;const stack=[[start,0]];
    while(stack.length){const frame=stack[stack.length-1],u=frame[0];
      if(frame[1]<graph[u].length){const v=graph[u][frame[1]++];if(v===parent[u])continue;
        if(disc[v]===-1){parent[v]=u;disc[v]=low[v]=time++;stack.push([v,0]);}else low[u]=Math.min(low[u],disc[v]);
      }else{stack.pop();const p=parent[u];if(p!==-1){low[p]=Math.min(low[p],low[u]);if(low[u]>disc[p])result.push([p,u]);}}
    }
  }
  return result;
}

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

Saved in this browser only. Private to you.

JavaScript