1192. Critical Connections in a Network (Hard)

Problem

There are n servers numbered 0 to n-1 connected by undirected edges. A critical connection (bridge) is an edge that, if removed, would disconnect the network.

Given the list of connections, return all critical connections.

Example

n = 4, connections = [[0,1],[1,2],[2,0],[1,3]] → [[1,3]]
- Removing [1,3] isolates server 3.
- Any other edge lies on the cycle 0-1-2-0 and is not critical.

LeetCode 1192 · Link · Hard

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach: Tarjan’s bridge-finding algorithm

Core idea: Run DFS and assign each node a discovery timestamp (disc). Also track low[v]: the lowest discovery time reachable from the subtree rooted at v, excluding the edge we arrived on.

low[v] = min(
    disc[v],
    min(disc[w] for w adjacent to v, not the parent),
    min(low[child] for child in DFS children of v)
)

An edge (u, v) (where v is the DFS child of u) is a bridge when:

low[v] > disc[u]

This means: no node reachable from v’s subtree can reach u or any ancestor of u via a back edge. Removing (u, v) therefore disconnects the graph.

Why low[v] > disc[u] (strict, not ≥): If low[v] == disc[u], the subtree of v can reach u itself (via a back edge to u), so there is an alternate path. The edge is not a bridge.

from collections import defaultdict

def critical_connections(n, connections):
    graph = defaultdict(list)                    # L1: O(1) init
    for u, v in connections:                     # L2: O(E) build adjacency
        graph[u].append(v)
        graph[v].append(u)

    disc = [-1] * n                              # L3: O(V) discovery times
    low = [0] * n                                # L4: O(V) low values
    bridges = []                                 # L5: O(1) result list
    timer = [0]                                  # L6: mutable counter (list trick)

    def dfs(node, parent):
        disc[node] = low[node] = timer[0]        # L7: O(1) assign timestamp
        timer[0] += 1                            # L8: O(1) increment

        for neighbor in graph[node]:             # L9: O(deg(node)) per call
            if neighbor == parent:               # L10: O(1) skip parent edge
                continue
            if disc[neighbor] == -1:             # L11: O(1) unvisited
                dfs(neighbor, node)              # L12: O(1) recurse
                low[node] = min(low[node], low[neighbor])   # L13: O(1) pull up
                if low[neighbor] > disc[node]:   # L14: O(1) bridge check
                    bridges.append([node, neighbor])
            else:                                # L15: back edge to visited node
                low[node] = min(low[node], disc[neighbor])  # L16: O(1) update low

    for i in range(n):                           # L17: handle disconnected components
        if disc[i] == -1:
            dfs(i, -1)

    return bridges

function criticalConnections(n: number, connections: number[][]): number[][] {
    const graph = new Map<number, number[]>();
    for (let i = 0; i < n; i++) graph.set(i, []);
    for (const [u, v] of connections) {          // L2: O(E) build adjacency
        graph.get(u)!.push(v);
        graph.get(v)!.push(u);
    }

    const disc = new Array(n).fill(-1);          // L3: O(V) discovery times
    const low = new Array(n).fill(0);            // L4: O(V) low values
    const bridges: number[][] = [];              // L5: O(1) result list
    let timer = 0;                               // L6: mutable counter

    function dfs(node: number, parent: number): void {
        disc[node] = low[node] = timer++;        // L7/L8: O(1) assign + increment

        for (const neighbor of graph.get(node)!) {  // L9: O(deg(node)) per call
            if (neighbor === parent) continue;   // L10: O(1) skip parent edge
            if (disc[neighbor] === -1) {         // L11: O(1) unvisited
                dfs(neighbor, node);             // L12: O(1) recurse
                low[node] = Math.min(low[node], low[neighbor]);  // L13: O(1) pull up
                if (low[neighbor] > disc[node]) bridges.push([node, neighbor]);  // L14: bridge check
            } else {                             // L15: back edge to visited node
                low[node] = Math.min(low[node], disc[neighbor]);  // L16: O(1) update low
            }
        }
    }

    for (let i = 0; i < n; i++) if (disc[i] === -1) dfs(i, -1);  // L17: handle disconnected
    return bridges;
}

// See 1192-critical-connections-approach2.go for the full runnable program.
// Core function uses Tarjan's bridge algorithm with disc/low arrays.
func criticalConnections(n int, connections [][]int) [][]int {
    graph := make([][]int, n)
    for _, c := range connections {                    // L2: O(E) build adjacency
        u, v := c[0], c[1]
        graph[u] = append(graph[u], v)
        graph[v] = append(graph[v], u)
    }
    disc := make([]int, n)
    low := make([]int, n)
    for i := range disc { disc[i] = -1 }              // L3: O(V) discovery times
    var bridges [][]int
    timer := 0
    var dfs func(node, parent int)
    dfs = func(node, parent int) {
        disc[node], low[node] = timer, timer           // L7: O(1) assign timestamp
        timer++                                        // L8: O(1) increment
        for _, neighbor := range graph[node] {         // L9: O(deg(node)) per call
            if neighbor == parent { continue }         // L10: O(1) skip parent edge
            if disc[neighbor] == -1 {                  // L11: O(1) unvisited
                dfs(neighbor, node)                    // L12: O(1) recurse
                if low[neighbor] < low[node] { low[node] = low[neighbor] }  // L13
                if low[neighbor] > disc[node] { bridges = append(bridges, []int{node, neighbor}) }  // L14
            } else if disc[neighbor] < low[node] {     // L15: back edge
                low[node] = disc[neighbor]             // L16: O(1) update low
            }
        }
    }
    for i := 0; i < n; i++ {                          // L17: handle disconnected
        if disc[i] == -1 { dfs(i, -1) }
    }
    return bridges
}

Where the time goes, line by line

Variables: V = n (nodes), E = len(connections).

Line	Per-call cost	Times executed	Contribution
L1-L2 (build graph)	$O(1)$	E	$O(E)$
L3-L4 (init arrays)	$O(1)$	V	$O(V)$
L7-L8 (timestamp)	$O(1)$	V	$O(V)$
L9 (neighbor loop)	$O(1)$ per neighbor	2E total	$O(E)$ ← dominates
L12 (recurse)	$O(1)$ dispatch	V	$O(V)$
L13/L14 (low update + bridge check)	$O(1)$	V	$O(V)$
L16 (back edge low)	$O(1)$	up to E	$O(E)$

Each node is visited exactly once; each edge is examined twice (once from each endpoint). Total work is $O(V + E)$ .

Complexity

Time: $O(V + E)$ . Each node and each edge processed once.
Space: $O(V + E)$ for the adjacency list, disc/low arrays, and recursion stack.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

final class Solution {
    func criticalConnections(_ n: Int, _ connections: [[Int]]) -> [[Int]] {
        var graph = Array(repeating: [Int](), count: n)
        for edge in connections { graph[edge[0]].append(edge[1]); graph[edge[1]].append(edge[0]) }
        var discovery = Array(repeating: -1, count: n), low = Array(repeating: 0, count: n), time = 0, bridges: [[Int]] = []
        func dfs(_ node: Int, _ parent: Int) {
            discovery[node] = time; low[node] = time; time += 1
            for neighbor in graph[node] where neighbor != parent {
                if discovery[neighbor] == -1 {
                    dfs(neighbor, node); low[node] = min(low[node], low[neighbor])
                    if low[neighbor] > discovery[node] { bridges.append([min(node, neighbor), max(node, neighbor)]) }
                } else { low[node] = min(low[node], discovery[neighbor]) }
            }
        }
        dfs(0, -1)
        bridges.sort { $0[0] == $1[0] ? $0[1] < $1[1] : $0[0] < $1[0] }
        return bridges
    }
}

Visualizing with the example

Nodes: 0, 1, 2, 3
Edges: 0-1, 1-2, 2-0, 1-3

DFS from 0 (parent=-1):
  disc[0]=0, low[0]=0
  visit 1 (parent=0):
    disc[1]=1, low[1]=1
    visit 2 (parent=1):
      disc[2]=2, low[2]=2
      neighbor 0: back edge -> low[2] = min(2, disc[0]=0) = 0
      neighbor 1: parent, skip
    low[1] = min(1, low[2]=0) = 0
    low[2]=0 > disc[1]=1? No -> not a bridge
    visit 3 (parent=1):
      disc[3]=3, low[3]=3
      neighbor 1: parent, skip
    low[1] = min(0, low[3]=3) = 0
    low[3]=3 > disc[1]=1? Yes -> BRIDGE [1,3]
  low[0] = min(0, low[1]=0) = 0
  low[1]=0 > disc[0]=0? No -> not a bridge
  neighbor 2: already visited, back edge
  low[0] = min(0, disc[2]=2) = 0

Result: [[1,3]]

Handling multi-edges

The parent-skip at L10 uses neighbor == parent. If the graph has multiple edges between the same pair of nodes, this single check skips all edges back to the parent, which is wrong for multi-graphs. For this problem LeetCode guarantees no duplicate edges, so the simple parent check is sufficient.

Summary

Step	What it detects
`disc[v]`	When `v` was first visited
`low[v]`	Earliest ancestor reachable from subtree of `v`
`low[v] > disc[u]`	No back edge from subtree of `v` reaches `u` or above: bridge

Tarjan’s bridge algorithm is the standard $O(V+E)$ solution for finding all bridges. The same DFS skeleton (with low values) also finds articulation points.

Test cases

from collections import defaultdict

def critical_connections(n, connections):
    graph = defaultdict(list)
    for u, v in connections:
        graph[u].append(v)
        graph[v].append(u)
    disc = [-1] * n
    low = [0] * n
    bridges = []
    timer = [0]

    def dfs(node, parent):
        disc[node] = low[node] = timer[0]
        timer[0] += 1
        for neighbor in graph[node]:
            if neighbor == parent:
                continue
            if disc[neighbor] == -1:
                dfs(neighbor, node)
                low[node] = min(low[node], low[neighbor])
                if low[neighbor] > disc[node]:
                    bridges.append([node, neighbor])
            else:
                low[node] = min(low[node], disc[neighbor])

    for i in range(n):
        if disc[i] == -1:
            dfs(i, -1)
    return bridges

def _run_tests():
    assert critical_connections(4, [[0,1],[1,2],[2,0],[1,3]]) == [[1,3]]
    assert critical_connections(2, [[0,1]]) == [[0,1]]
    assert critical_connections(3, [[0,1],[1,2],[0,2]]) == []
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function criticalConnections(n: number, connections: number[][]): number[][] {
    const graph = new Map<number, number[]>();
    for (let i = 0; i < n; i++) graph.set(i, []);
    for (const [u, v] of connections) {
        graph.get(u)!.push(v);
        graph.get(v)!.push(u);
    }
    const disc = new Array(n).fill(-1);
    const low = new Array(n).fill(0);
    const bridges: number[][] = [];
    let timer = 0;

    function dfs(node: number, parent: number): void {
        disc[node] = low[node] = timer++;
        for (const neighbor of graph.get(node)!) {
            if (neighbor === parent) continue;
            if (disc[neighbor] === -1) {
                dfs(neighbor, node);
                low[node] = Math.min(low[node], low[neighbor]);
                if (low[neighbor] > disc[node]) bridges.push([node, neighbor]);
            } else {
                low[node] = Math.min(low[node], disc[neighbor]);
            }
        }
    }

    for (let i = 0; i < n; i++) if (disc[i] === -1) dfs(i, -1);
    return bridges;
}

console.assert(JSON.stringify(criticalConnections(4, [[0,1],[1,2],[2,0],[1,3]])) === JSON.stringify([[1,3]]));
console.assert(JSON.stringify(criticalConnections(2, [[0,1]])) === JSON.stringify([[0,1]]));
console.assert(JSON.stringify(criticalConnections(3, [[0,1],[1,2],[0,2]])) === JSON.stringify([]));
console.log("all tests pass");

Number of Islands, DFS/BFS graph traversal fundamentals
Course Schedule, cycle detection with DFS
Network Delay Time, shortest paths on weighted graphs

DFS, the depth first traversal habit of following one branch before returning.
Graph Traversal, the visited set model for exploring nodes and edges without repetition.

1192. Critical Connections in a Network (Hard)

Problem

Try it yourself

Approach: Tarjan’s bridge-finding algorithm

Visualizing with the example

Handling multi-edges

Summary

Test cases

Related topics

Related concepts