Critical Connections in a Network: Tarjan's Bridge-Finding Algorithm

You are given n servers numbered from 0 to n - 1 and a list of undirected connections. A critical connection is an edge that, if removed, would disconnect some servers from each other. Return all critical connections.

This is LeetCode 1192: Critical Connections in a Network, and it is a textbook application of Tarjan's bridge-finding algorithm. The problem asks you to find every edge whose removal increases the number of connected components in the graph. In graph theory, these edges are called bridges.

Why this problem matters

Finding bridges in a network has direct real-world applications. In computer networks, a bridge is a single point of failure: if that link goes down, part of the network becomes unreachable. Network engineers use bridge detection to identify vulnerabilities and add redundancy. The same concept applies to road networks (which road closure would split a city in two?), power grids, and social networks (which friendship, if broken, would split a community?).

From an interview perspective, this problem tests whether you understand DFS beyond simple traversal. You need to track discovery timestamps, compute low-link values, and use the relationship between them to identify bridges. It is one of the hardest graph problems on LeetCode, but the core algorithm is elegant once you see how the pieces fit together.

The key insight

An edge (u, v) is a bridge if and only if node v (the child in the DFS tree) cannot reach any ancestor of u through a back edge. If v or any of its descendants has a back edge to an ancestor of u, then removing (u, v) would not disconnect the graph because there is an alternate path.

Tarjan's algorithm captures this with two values for each node:

1. disc[u]: the discovery time, which is when DFS first visits node u
2. low[u]: the smallest discovery time reachable from u through any combination of tree edges and back edges

After DFS returns from child v to parent u, if low[v] > disc[u], then v and its entire subtree have no back edge reaching u or any of u's ancestors. That means (u, v) is a bridge.

The solution

def criticalConnections(n, connections):
    graph = [[] for _ in range(n)]
    for u, v in connections:
        graph[u].append(v)
        graph[v].append(u)

    disc = [-1] * n
    low = [0] * n
    bridges = []
    timer = [0]

    def dfs(u, parent):
        disc[u] = low[u] = timer[0]
        timer[0] += 1

        for v in graph[u]:
            if v == parent:
                continue
            if disc[v] == -1:
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if low[v] > disc[u]:
                    bridges.append([u, v])
            else:
                low[u] = min(low[u], disc[v])

    dfs(0, -1)
    return bridges

Let's break this down.

We build an adjacency list for the undirected graph. Each connection adds edges in both directions. The disc array tracks when each node was first discovered by DFS, initialized to -1 to mark unvisited nodes. The low array tracks the earliest ancestor reachable from each node.

When DFS visits node u, it sets both disc[u] and low[u] to the current timer value, then increments the timer. For each neighbor v of u:

• If v is the parent of u in the DFS tree, skip it. We do not want to treat the edge we just came from as a back edge.
• If v is unvisited (disc[v] == -1), recurse into v. After returning, update low[u] = min(low[u], low[v]). If v found a back edge to an ancestor, u benefits from that too. Then check: if low[v] > disc[u], the subtree rooted at v cannot reach u or above, so (u, v) is a bridge.
• If v is already visited (a back edge), update low[u] = min(low[u], disc[v]). This records that u can reach the ancestor v through a back edge.

Visual walkthrough

Let's trace Tarjan's algorithm on a 4-node graph with edges 0-1, 1-2, 2-0, and 1-3. Watch how discovery times and low values are assigned, and how the bridge is identified when low[3] > disc[1].

The critical moment is Step 7. When DFS backtracks from node 3 to node 1, it checks low[3] (which is 3) against disc[1] (which is 1). Since 3 > 1, node 3 has no path back to node 1 or any of its ancestors without going through edge 1-3. That makes 1-3 a bridge.

Contrast this with edge 0-1. When DFS backtracks from node 1 to node 0, low[1] is 0 (because the cycle through node 2 reaches all the way back to node 0). Since low[1] (0) is not greater than disc[0] (0), edge 0-1 is not a bridge.

Complexity analysis

Time: DFS visits each node exactly once and processes each edge exactly once. Building the adjacency list takes O(E). The total is O(V + E).

Space: The adjacency list stores O(V + E). The disc and low arrays each use O(V). The recursion stack can go O(V) deep in the worst case (a straight-line graph). Total: O(V + E).

The building blocks

1. DFS with discovery timestamps

The foundation of Tarjan's algorithm is a DFS that assigns a monotonically increasing timestamp to each node as it is first visited:

timer = [0]

def dfs(u, parent):
    disc[u] = timer[0]
    timer[0] += 1
    for v in graph[u]:
        if disc[v] == -1:
            dfs(v, u)

This creates a DFS tree where every edge in the original graph is either a tree edge (connecting parent to child in DFS order) or a back edge (connecting a descendant to an ancestor). In an undirected graph, there are no cross edges or forward edges. This property is what makes the bridge-finding logic work.

2. Low-link value computation

The low-link value captures the earliest ancestor reachable from a node's subtree:

low[u] = disc[u]

for v in graph[u]:
    if v == parent:
        continue
    if disc[v] == -1:
        dfs(v, u)
        low[u] = min(low[u], low[v])
    else:
        low[u] = min(low[u], disc[v])

Each node starts with its own discovery time as its low value. Back edges pull the low value upward (to a smaller discovery time). Tree edges propagate low values from children to parents. After processing all neighbors, low[u] holds the smallest discovery time reachable from u's subtree.

Edge cases

• Tree graph (no cycles): Every edge is a bridge. Tarjan's algorithm correctly identifies all of them because no node has a back edge to pull its low value below its parent's discovery time.
• Complete graph: No edge is a bridge because removing any single edge still leaves all nodes connected through alternate paths. Every node's low value equals 0.
• Single edge: A graph with two nodes and one edge. That edge is trivially a bridge.
• Multiple components: The problem guarantees a connected graph, but if you needed to handle disconnected components, you would run DFS from each unvisited node in a loop.
• Parallel edges: If two nodes share multiple edges, neither is a bridge (removing one still leaves the other). The standard algorithm handles this by skipping the parent, but with parallel edges you need to skip only one occurrence of the parent edge, not all of them. The LeetCode problem states connections are unique, so this is not a concern here.

From understanding to recall

You have read through how discovery times and low-link values work together to find bridges. The logic is clean: if a child's subtree has no back edge reaching above its parent, the edge between them is a bridge. But reproducing this from scratch requires getting several details right. The timer incrementing. The parent check. The difference between updating low from low[v] (tree edge) versus disc[v] (back edge). The bridge condition low[v] > disc[u].

Spaced repetition turns these details into muscle memory. You practice writing the DFS with timestamps, the low-value propagation, and the bridge check from scratch at increasing intervals. After a few rounds, you stop thinking about which value to compare and just write it.

Graph algorithms are hard precisely because they have many moving parts. But each part is small and learnable. Tarjan's algorithm is just DFS plus two arrays plus one comparison. Drill the pieces separately, then put them together.

Related posts

• Course Schedule - Cycle detection with DFS, teaching the three-color marking pattern that is the directed-graph cousin of Tarjan's algorithm
• Redundant Connection - Union-find cycle detection, another way to reason about which edges are essential versus redundant in a graph
• Number of Islands - The essential grid DFS problem, building the traversal intuition that Tarjan's algorithm extends with timestamps and low values

CodeBricks breaks Critical Connections into its DFS-with-timestamps and low-link-computation building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a bridge-finding problem shows up in your interview, you do not re-derive the algorithm. You just write it.