Critical Connections in a Network

Critical Connections in a Network is the classic graph-bridge problem. It teaches Tarjan's bridge-finding algorithm: a single DFS that, with two numbers per node, finds every edge whose removal would split the network.

The slow way first

The brute-force idea: remove each edge one at a time, then run a full traversal to check whether the graph is still connected. With E edges and an O(V + E) traversal each, that is O(E · (V + E)) — far too slow for a large network.

The question to ask: can I detect a bridge in a single pass, without ever removing an edge? A bridge is an edge with no alternate route around it. If I can measure, for each node, whether its part of the graph has a "back door" to an ancestor, I can spot bridges directly.

The idea: discovery times and low-links

Run one DFS. Give each node two numbers:

• disc[u] — the discovery time, the order in which DFS first reached u.
• low[u] — the low-link, the smallest disc value reachable from u's subtree, including through one back-edge (an edge to an already-visited ancestor).

When DFS returns from a child v to its parent u, the edge u-v is a bridge exactly when low[v] > disc[u]. That inequality means nothing in v's subtree can reach u or anything above it without using the edge u-v itself — so cutting it disconnects them.

The key insight: a back-edge to an ancestor lowers low. If a subtree has any back-edge that climbs above u, the connecting edge is safe. If it has none, that edge is the only link — a bridge.

Walk through it

Step through the animation. DFS dives 0 → 1 → 2, and node 2 finds a back-edge 2-0 that pulls low[2] down to 0. That makes the whole triangle two-way connected, so none of its edges are bridges. Then DFS explores the tail 1 → 3 → 4. Node 4 is a dead end with no back-edge, so low[4] > disc[3]: edge 3-4 is a bridge. Likewise low[3] > disc[1], so 1-3 is a bridge too.

Pseudocode

build an adjacency list from connections
disc[*] = low[*] = -1            # -1 means "not visited yet"
timer = 0
 
dfs(u, parent):
    disc[u] = low[u] = timer; timer += 1
    for each neighbor v of u:
        if v is unvisited:                 # tree edge
            dfs(v, u)
            low[u] = min(low[u], low[v])
        else if v is not parent:           # back edge
            low[u] = min(low[u], disc[v])
        if low[v] > disc[u]:               # no back door around u-v
            record (u, v) as a bridge
 
dfs(0, -1)
return all recorded bridges

The Python solution

def critical_connections(n, connections):
    graph = build_adjacency(connections)
    disc, low = [-1] * n, [-1] * n
    bridges = []
    timer = [0]
 
    def dfs(u, parent):
        disc[u] = low[u] = timer[0]
        timer[0] += 1
        for v in graph[u]:
            if disc[v] == -1:            # tree edge
                dfs(v, u)
                low[u] = min(low[u], low[v])
            elif v != parent:            # back edge
                low[u] = min(low[u], disc[v])
            if low[v] > disc[u]:
                bridges.append([u, v])
 
    dfs(0, -1)
    return bridges

• disc and low start at -1, which doubles as the "not visited yet" marker.
• timer is a one-element list so the nested dfs can mutate it (a shared counter).
• When v is unvisited we recurse (a tree edge), then fold the child's low into the parent.
• elif v != parent handles a back-edge to an ancestor: we lower low[u] toward disc[v]. Skipping parent avoids treating the edge we just came down as a back-edge.
• low[v] > disc[u] is the bridge test: the child reached nothing at or above u, so the edge is critical.

Complexity

We visit every node and edge once. The extra space is the adjacency list plus the disc, low, and recursion stack — all linear in the graph size.

When this pattern shows up

Practice