Find every link whose loss splits a network: one DFS stamps discovery times, carries low links up, and cuts where a child can't reach back.
▼The problem
LeetCode 1192 (Hard). There are n servers 0 .. n-1 and undirected connections between them (the network is connected, no repeated connections). A connection is critical if removing it leaves some server unable to reach some other server. Return every critical connection, in any order. These are the graph's *bridges*.
Examples (LeetCode's): n = 4, connections = [[0,1],[1,2],[2,0],[1,3]] → [[1,3]] (0, 1, 2 are a loop; 3 hangs off 1) and n = 2, connections = [[0,1]] → [[0,1]].
The solution
def critical_connections(n, connections):
graph = [[] for _ in range(n)]
for a, b in connections:
graph[a].append(b); graph[b].append(a)
disc, low, out = [-1] * n, [0] * n, []
clock = iter(range(n))
def dfs(u, parent):
disc[u] = low[u] = next(clock)
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]:
out.append([u, v])
else:
low[u] = min(low[u], disc[v])
dfs(0, -1)
return outTranscript
Critical Connections in a Network. n servers are joined by cables. A cable is critical if cutting it cuts some servers off. Return them all.
Here, zero, one and two form a loop, and three hangs off one. Cut a loop cable and power goes around, so only one to three is critical. With two servers, their one cable is critical.
The slow way: cut each cable, then search to see if all still have power. Two of these eight cuts cause a blackout, but that's a whole search per cable: E times V plus E.
Tarjan's idea: one depth-first search. Each server gets a discovery time and a low: the earliest time its subtree reaches by one back edge, skipping the cable to its parent. If a child's low beats its parent's time, that side has no way back: the cable is a bridge.
In code, stamp disc and low on entry. For each neighbor but the parent: recurse if it's new, pull its low up, and check it against disc. If seen, take its time.
Walking it: zero gets time zero, one gets one, two gets two. Two sees zero by a back edge, so its low drops to zero, and so does one's. Three gets time three, a dead end. Three beats one's time: one to three is critical. The loop cables keep low zero: safe.
One pass over servers and cables: O of V plus E time and space.
Stamp the times, carry the lows up, cut where low beats disc. That's Critical Connections.