Stage 4: Advanced Techniques·Advanced Graph

Hard#11929 min readGraphDFSTarjanLeetCode

Critical Connections in a Network

Tarjan's bridges with low-link DFS

Tarjan’s bridge-finding algorithm. Must-know for systems interviews.

Published Apr 16, 2026

Problem

You're given an undirected connected network of n servers (labeled 0..n-1) and a list of connections where connections[i] = [a, b] is a bidirectional link between servers a and b.

A critical connection (a.k.a. bridge) is an edge whose removal disconnects the graph. Return all critical connections, in any order.

Input

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

Output

[[1,3]]

Explanation

Removing 1-3 isolates server 3 from the rest. The triangle 0-1-2 has no bridges because any single edge can be routed around.

Input

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

Output

[[0,1]]

Explanation

The lone edge is the only way to connect the two servers — removing it disconnects them.

Input

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

Output

[]

Explanation

A 4-cycle has no bridges — every edge can be bypassed by walking around the other way.

Intuition

A brute-force check removes each edge and asks "is the graph still connected?" via DFS/BFS. That works but costs O(E · (V + E)).

The elegant observation: an edge (u, v) is a bridge if and only if there is no back-edge from the subtree rooted at v (in a DFS tree) that reaches u or any ancestor of u. Tarjan's algorithm captures this with two numbers per node:

disc[v] — the time v was first discovered by DFS (increasing counter).
low[v] — the lowest disc reachable from v's DFS subtree using tree edges plus at most one back edge.

If low[v] > disc[u] for tree edge u → v, then v's subtree cannot reach u or above — removing (u, v) disconnects them. That's a bridge.

Approach

Brute Force — Remove Each Edge

TimeO(E · (V + E))

SpaceO(V + E)

For each edge, temporarily remove it, run a DFS from any vertex, and check whether all n nodes are still reachable. Simple and obviously correct, but O(E^2) in the worst case.

impl Solution {
    pub fn critical_connections(n: i32, connections: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let n = n as usize;
        let mut result: Vec<Vec<i32>> = Vec::new();

        for skip in 0..connections.len() {
            let mut graph: Vec<Vec<usize>> = vec![Vec::new(); n];
            for (i, e) in connections.iter().enumerate() {
                if i == skip { continue; }
                graph[e[0] as usize].push(e[1] as usize);
                graph[e[1] as usize].push(e[0] as usize);
            }

            let mut visited = vec![false; n];
            let mut stack = vec![0usize];
            visited[0] = true;
            let mut count = 1;
            while let Some(u) = stack.pop() {
                for &v in &graph[u] {
                    if !visited[v] {
                        visited[v] = true;
                        count += 1;
                        stack.push(v);
                    }
                }
            }

            if count < n {
                result.push(connections[skip].clone());
            }
        }

        result
    }
}

Rust · runnable

function criticalConnections(n: number, connections: number[][]): number[][] {
  const result: number[][] = [];

  for (let skip = 0; skip < connections.length; skip++) {
    const graph: number[][] = Array.from({ length: n }, () => []);
    for (let i = 0; i < connections.length; i++) {
      if (i === skip) continue;
      const [a, b] = connections[i];
      graph[a].push(b);
      graph[b].push(a);
    }

    const visited = new Array<boolean>(n).fill(false);
    const stack: number[] = [0];
    visited[0] = true;
    let count = 1;
    while (stack.length > 0) {
      const u = stack.pop()!;
      for (const v of graph[u]) {
        if (!visited[v]) {
          visited[v] = true;
          count++;
          stack.push(v);
        }
      }
    }

    if (count < n) result.push(connections[skip]);
  }

  return result;
}

TypeScript · runnable

Tarjan's Bridges (Low-Link DFS)

TimeO(V + E)

SpaceO(V + E)

Recommended

Run a single DFS. Assign each node a discovery time disc[v] on first visit. Initialize low[v] = disc[v]. When recursing into an unvisited neighbor w via the tree edge v → w, recurse first, then update low[v] = min(low[v], low[w]). If after the recursive return low[w] > disc[v], then (v, w) is a bridge.

For back edges (to a non-parent already-visited neighbor), update low[v] = min(low[v], disc[neighbor]). Skip the parent edge so we don't mistake the tree edge itself for a back edge. For safety with parallel edges, track the edge by index rather than endpoint.

impl Solution {
    pub fn critical_connections(n: i32, connections: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let n = n as usize;
        let mut graph: Vec<Vec<(usize, usize)>> = vec![Vec::new(); n];
        for (i, e) in connections.iter().enumerate() {
            let (u, v) = (e[0] as usize, e[1] as usize);
            graph[u].push((v, i));
            graph[v].push((u, i));
        }

        let mut disc = vec![-1i32; n];
        let mut low = vec![0i32; n];
        let mut timer = 0i32;
        let mut bridges: Vec<Vec<i32>> = Vec::new();

        // Iterative DFS stack of (node, parent_edge_index, neighbor_iter_index).
        let mut stack: Vec<(usize, i32, usize)> = Vec::new();
        for start in 0..n {
            if disc[start] != -1 { continue; }
            disc[start] = timer;
            low[start] = timer;
            timer += 1;
            stack.push((start, -1, 0));

            while let Some(&(u, parent_edge, idx)) = stack.last() {
                if idx < graph[u].len() {
                    let (v, edge_i)= graph[u][idx];
                    stack.last_mut().unwrap().2 = 1;
                    if edge_i as i32= parent_edge {
                        continue;
                    }
                    if disc[v]= -1 {
                        disc[v]= timer;
                        low[v]= timer;
                        timer = 1;
                        stack.push((v, edge_i as i32, 0));
                    } else {
                        low[u]= low[u].min(disc[v]);
                    }
                } else {
                    stack.pop();
                    if let Some(&(p, _, _))= stack.last() {
                        low[p]= low[p].min(low[u]);
                        if low[u] > disc[p] {
                            bridges.push(connections[parent_edge as usize].clone());
                        }
                    }
                }
            }
        }

        bridges
    }
}

Rust · runnable

function criticalConnections(n: number, connections: number[][]): number[][] {
  const graph: Array<Array<[number, number]>> = Array.from({ length: n }, () => []);
  for (let i = 0; i < connections.length; i++) {
    const [u, v]= connections[i];
    graph[u].push([v, i]);
    graph[v].push([u, i]);
  }

  const disc= new Array<number>(n).fill(-1);
  const low = new Array<number>(n).fill(0);
  let timer = 0;
  const bridges: number[][] = [];

  // Iterative DFS frame: [node, parentEdgeIndex, neighborCursor].
  const stack: Array<[number, number, number]> = [];
  for (let start = 0; start < n; start++) {
    if (disc[start] = -1) continue;
    disc[start]= timer;
    low[start]= timer;
    timer++;
    stack.push([start, -1, 0]);

    while (stack.length > 0) {
      const top = stack[stack.length - 1];
      const [u, parentEdge, idx] = top;
      if (idx < graph[u].length) {
        const [v, edgeI]= graph[u][idx];
        top[2]++;
        if (edgeI= parentEdge) continue;
        if (disc[v]= -1) {
          disc[v]= timer;
          low[v]= timer;
          timer++;
          stack.push([v, edgeI, 0]);
        } else {
          low[u]= Math.min(low[u], disc[v]);
        }
      } else {
        stack.pop();
        if (stack.length > 0) {
          const parent = stack[stack.length - 1];
          const p = parent[0];
          low[p] = Math.min(low[p], low[u]);
          if (low[u] > disc[p]) {
            bridges.push(connections[parentEdge]);
          }
        }
      }
    }
  }

  return bridges;
}

TypeScript · runnable

A few notes:

Iterative DFS avoids stack overflow on 100k-node inputs (LeetCode's constraint).
Track edge index, not parent node — parallel edges between the same pair are rare in this problem but the index trick keeps us correct.
disc and low share the same type — we use -1 as the "unvisited" sentinel.

Trace

Tarjan's DFS on n = 4, connections = [[0,1],[1,2],[2,0],[1,3]] starting at node 0:

step	node	action	disc	low
1	0	enter (timer=0)	[0,-,-,-]	[0,-,-,-]
2	1	enter via edge 0	[0,1,-,-]	[0,1,-,-]
3	2	enter via edge 1	[0,1,2,-]	[0,1,2,-]
4	2	back edge 2→0	[0,1,2,-]	[0,1,0,-]
5	2	exit to 1	[0,1,2,-]	[0,0,0,-]
6	3	enter via edge 3	[0,1,2,3]	[0,0,0,3]
7	3	exit to 1	[0,1,2,3]	[0,0,0,3]
8	1	check 3: low[3]=3 > disc[1]=1 → bridge (1,3)	[0,1,2,3]	[0,0,0,3]

The triangle 0-1-2 has low values all at 0 (the entry time), so no bridges there. Edge (1,3) is flagged because node 3 has no back-edge to anything at or above node 1.

Edge cases

Tree (no cycles) — every edge is a bridge; the algorithm reports n - 1 of them.
Single cycle — no bridges; every node can reach its predecessor via the rest of the ring.
Parallel edges — the edge-index trick prevents misclassifying a repeated edge as a back edge to the parent.
Multiple connected components — the outer for start in 0..n loop restarts DFS in each component. The problem guarantees connectivity, but this generalizes cleanly.

💡

Tip

Tarjan's bridges also find articulation points with one extra check — an internal node u is an articulation point if any child w has low[w] >= disc[u]. Same DFS, weaker inequality.

Takeaway

low[v] captures "the oldest ancestor reachable from v's subtree using at most one back edge" — and inequality against disc tells you whether a tree edge can be bypassed.

This DFS pattern shows up directly in:

Network reliability analysis — bridges are single points of failure between subnets.
Social graph analysis — articulation points identify influential brokers.
Compilers — dominator trees and strongly-connected components share the same low-link machinery.

Medium#787

Cheapest Flights Within K Stops

Bellman-Ford with K rounds. You already know this from your arb bot.

Hard#1489

Find Critical and Pseudo-Critical Edges in MST

Kruskal’s + edge classification. Deep graph understanding.

Hard#1579

Remove Max Edges to Keep Graph Traversable

Dual Union-Find. Process shared edges first (greedy).