Hints — p68 Critical Connections in a Network

Hint 1. A bridge (critical edge) is an edge whose removal disconnects the graph. Brute force: for each edge, remove it and run DFS to check connectivity. O(E·(V+E)) — too slow for LC’s constraints (n up to 10⁵).

Hint 2. Tarjan’s bridge algorithm finds all bridges in a single DFS pass, O(V+E). Assign each node two timestamps:

• disc[u] = when u was first discovered (DFS order).
• low[u] = lowest disc reachable from u’s subtree via tree edges + AT MOST ONE back edge.

Hint 3. Bridge condition: a tree edge (u, v) where v is u’s DFS child is a bridge ⟺ low[v] > disc[u]. (Meaning: v’s subtree can’t reach above u via any back edge → cutting (u,v) disconnects.)

Hint 4. Computing low[u]:

• Initialize low[u] = disc[u].
• For each neighbor v: if v is the PARENT (the edge you came in on), skip.
• If v is already visited (back edge): low[u] = min(low[u], disc[v]). Use disc[v], not low[v] — this is the most common bug.
• If v is unvisited (tree edge): recurse, then low[u] = min(low[u], low[v]). Check bridge condition.

Hint 5. LC 1192’s n=10⁵ blows Python’s default recursion limit (1000). You must convert to iterative DFS with an explicit stack carrying (node, parent_edge_id, iterator over neighbors). After popping a child, integrate its low into the parent and check the bridge condition.

If stuck: see solution.py.