Critical Connections LeetCode 1192 — Tarjan

LeetCode 1192 Critical Connections in a Network gives you n servers labeled 0 to n-1 connected by undirected edges. Your task is to find all critical connections — edges whose removal increases the number of connected components, splitting the network. These edges are called bridges.

The problem is essentially a bridge-finding problem on an undirected graph. A bridge is any edge that, if removed, causes some server to become unreachable from others. In network design, bridges represent single points of failure: redundant paths eliminate bridges, but when none exist, the edge is critical.

You must return the list of all such critical connections. The order of results does not matter, and each edge can be returned in any order. The challenge is doing this efficiently for graphs with up to 100,000 nodes and 100,000 edges.

A bridge in graph theory is an edge whose removal increases the number of connected components. Equivalently, an edge (u, v) is a bridge if and only if there is no alternative path between u and v that avoids that edge. If removing (u, v) still leaves u and v connected through other edges, then (u, v) is not a bridge.

Bridges are the weak links of a network. In a fully redundant network (every node has at least two disjoint paths to every other node), there are no bridges. Every time you find a bridge, you've found a structural vulnerability: that single edge is the only way to traverse between the two partitions it connects.

Identifying bridges is fundamental in network reliability analysis, where engineers need to know which connections, if cut, would partition the network. Tarjan's algorithm finds all bridges in a single DFS pass — no need to test each edge individually, which would be O(E*(V+E)) brute force.

Tarjan's bridge-finding algorithm uses DFS and assigns two values to each node: disc[u] (discovery time — the step at which u was first visited) and low[u] (the minimum discovery time reachable from u's subtree via back edges). The timer increments with each new node visited.

The low-link value low[u] captures whether u or any descendant in the DFS tree has a back edge reaching an ancestor above u. If low[u] is small (equal to disc[u] or smaller), there's an alternative path upward. If low[u] equals disc[u], it means u itself is an articulation point for its subtree.

Initially, both disc[u] and low[u] are set to the current timer value when u is first visited. As DFS explores neighbors, low[u] is updated by taking the minimum of its current value and the low values of children (after recursion) and the disc values of back-edge neighbors.

The bridge detection condition is: edge (u, v) is a bridge if low[v] > disc[u]. This means v's entire DFS subtree cannot reach u or any ancestor of u via a back edge — the only path from v's subtree back to u is through edge (u, v) itself. Remove that edge and the subtree becomes disconnected.

If low[v] <= disc[u], then somewhere in v's subtree there exists a back edge that reaches u or an ancestor of u. This alternative path means removing (u, v) would still leave v's subtree connected to u's part of the graph. Therefore (u, v) is not a bridge.

This condition is checked immediately after the recursive DFS call returns from v. At that point, low[v] has been fully computed — it reflects the earliest discovery time reachable from v's entire subtree. The comparison against disc[u] (not disc[v] or low[u]) is what makes this work correctly.

The DFS maintains a global timer (or pass it as a mutable reference). When visiting node u with parent p, set disc[u] = low[u] = timer and increment timer. Then iterate over all neighbors v of u. Skip v if v == p (the direct tree-edge parent) to avoid treating the back-traversal of the tree edge as a back edge.

For each unvisited neighbor v, recurse: dfs(v, u). After returning, update low[u] = min(low[u], low[v]). Then check the bridge condition: if low[v] > disc[u], append (u, v) to the results list.

For each already-visited neighbor v that is not the parent, update low[u] = min(low[u], disc[v]). This is the back-edge update — it records that u can reach v (an ancestor) directly, tightening the low-link value.

The Python solution builds an adjacency list from the connections input, initializes disc and low arrays of size n to -1, and uses a nested DFS function with a mutable timer list [0]. The DFS is called from node 0 with parent -1. Total time complexity is O(V+E) — each node and edge is visited once.

In Java, the same structure applies: int[] disc and int[] low initialized to -1, a List<List<Integer>> adjacency list, and a recursive dfs(int u, int parent) method. An int[] timer = {0} provides mutable state for the timer across recursive calls. Results accumulate in a List<List<Integer>>.

Space complexity is O(V+E) for the adjacency list plus O(V) for the disc, low, and recursion stack. For graphs with up to 100,000 nodes, the recursion depth can hit stack limits in Python — consider an iterative DFS with explicit stack, or increase recursion limit with sys.setrecursionlimit.

Redundant Connection (LC 684) is the complement problem: instead of finding bridges (edges whose removal disconnects), it finds the one extra edge that creates a cycle in an otherwise acyclic graph. Where Tarjan finds structural weaknesses, Union-Find finds structural redundancies. Both are fundamental graph structure algorithms.

Number of Provinces (LC 547) and graph connectivity problems share the DFS/BFS traversal foundation. Finding connected components, bridges, and articulation points all rely on systematic graph traversal. Tarjan's algorithm for SCCs (strongly connected components) in directed graphs uses a similar disc/low framework.

Minimum Spanning Tree algorithms (Kruskal's and Prim's) also deal with graph connectivity and edge criticality. A bridge in an undirected graph corresponds to an edge that must appear in every spanning tree. Understanding bridges, cycles, and MSTs together gives a complete picture of graph structural analysis.