Critical connections in a network

Depth-First Search Graph Theory Biconnected Component

59.3% acceptance

Feb 25, 2026

6676

192

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn critical_connections(n: i32, connections: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    // Tarjan's bridge finding algorithm
    let n = n as usize;
    let mut adj = vec![vec![]; n];
    for c in &connections {
      let (u, v) = (c[0] as usize, c[1] as usize);
      adj[u].push(v);
      adj[v].push(u);
    }
    let mut disc = vec![u32::MAX; n];
    let mut low = vec![0u32; n];
    let mut timer = 0u32;
    let mut result = Vec::new();
    // Iterative DFS: stack holds (node, parent, adj_index)
    let mut stack: Vec<(usize, usize, usize)> = Vec::new();
    for start in 0..n {
      if disc[start] != u32::MAX { continue; }
      stack.push((start, usize::MAX, 0));
      disc[start] = timer;
      low[start] = timer;
      timer += 1;
      while !stack.is_empty() {
        let (u, parent, idx) = stack.last_mut().unwrap();
        let u_val = *u;
        let parent_val = *parent;
        if *idx < adj[u_val].len() {
          let v = adj[u_val][*idx];
          *idx += 1;
          if v == parent_val { continue; }
          if disc[v] == u32::MAX {
            disc[v] = timer;
            low[v] = timer;
            timer += 1;
            stack.push((v, u_val, 0));
          } else {
            low[u_val] = low[u_val].min(disc[v]);
          }
        } else {
          stack.pop();
          if let Some(&(pu, _, _)) = stack.last() {
            if low[u_val] > disc[pu] {
              result.push(vec![pu as i32, u_val as i32]);
            }
            low[pu] = low[pu].min(low[u_val]);
          }
        }
      }
    }
    result
  }
}