Critical Connections in a Network — Hard Problem & Solution

Problem statement

n CodeKairo servers numbered 0 … n - 1 are joined by undirected connections, forming one network in which every server can reach every other.

A connection is critical if removing it leaves some server unable to reach some other. Return all critical connections, each written as [smaller, larger], sorted in increasing order.

Example 1

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: The triangle `0-1-2` survives any single removal; the link to server 3 does not.

Example 2

Input: n = 2, connections = [[0,1]]
Output: [[0,1]]

Example 3

Input: n = 3, connections = [[0,1],[1,2],[2,0]]
Output: []
Explanation: A cycle has no critical connection.

Constraints

• 2 <= n <= 10^5
• n - 1 <= connections.length <= 10^5
• 0 <= connections[i][0], connections[i][1] < n
• connections[i][0] != connections[i][1]
• There are no repeated connections.
• The answer is returned as [smaller, larger] pairs in increasing order.

How to solve Critical Connections in a Network

Tarjan's bridge algorithm. During a depth-first search, give each node a discovery time disc and a value low — the earliest discovery time reachable from its subtree using at most one back edge. The tree edge (p, u) is a bridge when low[u] > disc[p].

Approach

1. Depth-first search from each unvisited node, stamping disc and initialising low to it.
2. On a tree edge to v, recurse and then low[p] = min(low[p], low[v]).
3. On a back edge to an already-seen v, low[u] = min(low[u], disc[v]).
4. Record (p, u) when low[u] > disc[p], then sort the results.

Why it works

low[u] > disc[p] says nothing under u has a second way back to p or above it, so cutting that edge disconnects the subtree — which is exactly what "critical" means. The one subtlety is skipping the edge you arrived on: skipping by neighbour would wrongly ignore a genuine parallel edge, so the search skips the specific edge index instead. The traversal here is written with an explicit stack because n reaches 100 000 and a path-shaped network would overflow the call stack.

Complexity

• Time — O(n + m)
• Space — O(n + m)

Pitfalls

• Comparing low[u] against low[p] instead of disc[p] misses bridges.
• Skipping every edge back to the parent node hides parallel edges; skip the one edge index.
• The back-edge update uses disc[v], not low[v].

Reference solution

Python

from typing import List
import sys

def criticalConnections(n: int, connections: List[List[int]]) -> List[List[int]]:
    head = [-1] * n
    cap = max(1, len(connections) * 2)
    nxt = [-1] * cap
    to = [0] * cap
    ec = 0
    for u, v in connections:
        to[ec] = v; nxt[ec] = head[u]; head[u] = ec; ec += 1
        to[ec] = u; nxt[ec] = head[v]; head[v] = ec; ec += 1
    disc = [-1] * n
    low = [0] * n
    timer = 0
    bridges = []
    for s in range(n):
        if disc[s] >= 0:
            continue
        disc[s] = low[s] = timer
        timer += 1
        stack = [(s, -1, head[s])]
        while stack:
            u, in_edge, e = stack[-1]
            if e >= 0:
                stack[-1] = (u, in_edge, nxt[e])
                if in_edge >= 0 and (e ^ 1) == in_edge:
                    continue
                v = to[e]
                if disc[v] < 0:
                    disc[v] = low[v] = timer
                    timer += 1
                    stack.append((v, e, head[v]))
                elif disc[v] < low[u]:
                    low[u] = disc[v]
            else:
                stack.pop()
                if stack:
                    p = stack[-1][0]
                    if low[u] < low[p]:
                        low[p] = low[u]
                    if low[u] > disc[p]:
                        bridges.append([min(p, u), max(p, u)])
    bridges.sort()
    return bridges

JavaScript

var criticalConnections = function(n, connections) {
    var i;
    var head = [];
    for (i = 0; i < n; i++) head.push(-1);
    var cap = Math.max(1, connections.length * 2);
    var nxt = [], to = [];
    for (i = 0; i < cap; i++) { nxt.push(-1); to.push(0); }
    var ec = 0;
    for (i = 0; i < connections.length; i++) {
        var u0 = connections[i][0], v0 = connections[i][1];
        to[ec] = v0; nxt[ec] = head[u0]; head[u0] = ec; ec++;
        to[ec] = u0; nxt[ec] = head[v0]; head[v0] = ec; ec++;
    }
    var disc = [], low = [];
    for (i = 0; i < n; i++) { disc.push(-1); low.push(0); }
    var timer = 0;
    var bridges = [];
    var stackNode = [], stackEdge = [], stackIter = [];
    for (var s = 0; s < n; s++) {
        if (disc[s] >= 0) continue;
        disc[s] = low[s] = timer++;
        stackNode.push(s);
        stackEdge.push(-1);
        stackIter.push(head[s]);
        while (stackNode.length > 0) {
            var u = stackNode[stackNode.length - 1];
            var e = stackIter[stackIter.length - 1];
            if (e >= 0) {
                stackIter[stackIter.length - 1] = nxt[e];
                var inEdge = stackEdge[stackEdge.length - 1];
                if (inEdge >= 0 && (e ^ 1) === inEdge) continue;
                var v = to[e];
                if (disc[v] < 0) {
                    disc[v] = low[v] = timer++;
                    stackNode.push(v);
                    stackEdge.push(e);
                    stackIter.push(head[v]);
                } else if (disc[v] < low[u]) {
                    low[u] = disc[v];
                }
            } else {
                stackNode.pop();
                stackEdge.pop();
                stackIter.pop();
                if (stackNode.length > 0) {
                    var p = stackNode[stackNode.length - 1];
                    if (low[u] < low[p]) low[p] = low[u];
                    if (low[u] > disc[p]) {
                        bridges.push([Math.min(p, u), Math.max(p, u)]);
                    }
                }
            }
        }
    }
    bridges.sort(function(x, y) { return (x[0] - y[0]) || (x[1] - y[1]); });
    return bridges;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More depth-first search problems

• Minimum Time to Visit a Cell In a Grid Hard
• Checking Existence of Edge Length Limited Paths Hard
• Find All People With Secret Hard
• Minimum Obstacle Removal to Reach Corner Hard
• Number of Good Paths Hard
• Number of Restricted Paths From First to Last Node Hard