p68 — Critical Connections in a Network

Source: LeetCode 1192 · Hard · Topics: Graph, Tarjan, Bridges, DFS Companies (2024–2025): Amazon (high), Google (medium-high), Meta (medium), Microsoft (medium) Loop position: Tarjan’s bridge-finding algorithm. The named algorithm interviewers reach for at L5+. Tests disc / low invariants — the single most-tested DFS-with-timestamps pattern after standard DFS itself.

1. Quick Context

Undirected graph (n servers, connections list). A bridge (a.k.a. critical edge / cut edge) is an edge whose removal disconnects the graph. Return all bridges.

Tarjan’s algorithm (1972): single DFS with two timestamps per node:

disc[u] = DFS discovery order (when u was first visited).
low[u] = lowest disc reachable from u’s subtree via tree edges OR ONE back-edge.

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

O(V + E). Single DFS pass.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/critical-connections-in-a-network/

STOP. 40-min timer. This is HARD.

3. Prerequisite Concepts

DFS tree (tree edges, back edges, forward edges, cross edges).
For UNDIRECTED graphs: only tree edges and back edges (no forward or cross).
DFS timestamps (discovery time).
Iterative DFS — recursion limit issue on LC (n up to 10⁵).

4. How to Approach (FRAMEWORK 1–9)

1. Restate: Find all edges whose removal increases the number of connected components by 1.

2. Clarify: Multi-edges? (LC 1192 says no.) Self-loops? (Never bridges.) Connected initially? (Usually yes; algorithm handles disconnected anyway.)

3. Examples: n=4, connections=[[0,1],[1,2],[2,0],[1,3]] → [[1,3]]. The triangle 0-1-2 has no bridges; the spoke 1-3 is critical.

5. Brute force: Remove each edge, check connectivity with DFS, restore. O(E · (V+E)).

6. Target: O(V + E) via Tarjan.

7. Pattern: Tarjan bridge-finding (DFS with disc and low).

8. Develop: see solution.py.

9. Test: triangle (no bridges); single edge (it’s a bridge); two triangles joined by one edge (that edge is the bridge); tree (every edge is a bridge).

In a DFS tree of an undirected graph, the only non-tree edges are back edges (to an ancestor). Forward and cross edges don’t exist (because we’d have visited the destination already by the time we go back up; but in undirected, “back” and “forward” collapse).

For tree edge (u, v) (v is u’s child): removing it disconnects v’s subtree from the rest IFF no back edge from v’s subtree goes to u or an ancestor of u. That’s exactly low[v] > disc[u].

If low[v] ≤ disc[u], there’s an alternate path — bridge is NOT critical.

6.2 Computing `low[u]` precisely

disc[u] = timer; low[u] = timer; timer += 1
for each neighbor v of u:
    if v is parent: continue   # don't go back along the SAME edge we came in
    if disc[v] != -1:          # already visited (back edge)
        low[u] = min(low[u], disc[v])
    else:                      # tree edge
        dfs(v, parent=u)
        low[u] = min(low[u], low[v])
        if low[v] > disc[u]:
            bridges.append((u, v))

Subtle: When taking back edge to neighbor v, use disc[v], NOT low[v]. (Using low[v] would be wrong — we want the lowest disc reachable, and from a back edge we directly reach v.)

6.3 The “parent” exclusion subtlety (multi-edges)

The “don’t go back to parent” rule works only if there are NO multi-edges. With multi-edges, the second edge to parent is a genuine back edge.

Robust fix: track which EDGE INDEX you came in on (not just the parent node). Skip exactly that one edge, not all edges to the parent node.

6.4 Iterative DFS — required for LC 1192

LC constraints (n up to 10⁵) blow Python’s default recursion limit of 1000. Must convert to iterative DFS with an explicit stack.

Iterative Tarjan is tricky: each stack frame remembers its iterator over neighbors AND a “child index” to know where to resume after a child returns. See solution.py.

6.5 Bridges vs articulation points (cut vertices)

Bridge: edge whose removal disconnects.
Articulation point: vertex whose removal disconnects.

Different concepts! Same algorithm framework with different conditions:

Bridge: low[v] > disc[u] (strictly greater).
Articulation point (non-root): low[v] ≥ disc[u] (greater or equal).
Articulation root: root is articulation if it has ≥ 2 DFS-children.

6.6 Block-cut tree

The 2-edge-connected components (sub-graphs with no bridges) form a forest when contracted; the bridges are the inter-component edges. This block-cut tree is the canonical structure for “how is this graph held together.”

6.7 Online / dynamic bridge maintenance

Static bridges in O(V+E). For DYNAMIC (edges added/removed), Holm-Lichtenberg-Thorup gives O(log² n) per operation. Advanced; mention only at Staff+.

6.8 Generalization: k-edge-connectivity

Bridge = “1-edge-connectivity weakness.” For 2-edge-connectivity (no 2 edges whose removal disconnects), the algorithm extends but becomes more involved. Gomory-Hu trees compute all-pairs k-edge-connectivity.

7. Anti-Pattern Analysis

Recursive DFS for LC 1192 — Python recursion limit (default 1000); n up to 10⁵; stack overflow on linear chains.
Use low[v] instead of disc[v] on back edges — silently miscomputes low; wrong answer.
Exclude parent by NODE not by EDGE — fails on multi-edges.
Compare low[v] >= disc[u] — that’s the ARTICULATION POINT condition; for bridges use strict >.
Build adjacency without edge indices — multi-edge subtlety can’t be handled.
Brute O(E·(V+E)) — works for small inputs, TLE on LC 1192’s constraints.

8. Skills & Takeaways

Tarjan’s disc/low framework — the workhorse of advanced DFS algorithms.
The DFS tree structure on undirected graphs (only tree + back edges).
Bridge ⟺ low[v] > disc[u]; articulation point uses ≥ (slight but important).
Iterative DFS with neighbor iterators for large inputs.

9. When to Move On

Implement iterative Tarjan bridge-finder cold in 30 min.
Explain why low[v] > disc[u] characterizes bridges in 90 seconds.
Solve articulation points (LC has it as a related problem) with the modified condition.
Recognize the algorithm by name when an interviewer says “find all critical edges.”

10. Company Context

Amazon: L6 onsite; service-mesh “find single-point-of-failure connections.”
Google: L6; SRE networking, fault-tolerant topology design.
Meta: E6; data-center inter-rack links analysis.
Microsoft: L65+; Azure VNet topology.

Scorecard for strong: “Named Tarjan, used disc/low, wrote iterative DFS for scale, used edge indices to handle multi-edges, distinguished bridges from articulation points.”

11. Interviewer’s Lens

Signal	Junior	Mid	Senior	Staff+
Algorithm	Brute O(E·(V+E))	Recursive Tarjan (TLE)	Iterative Tarjan correct	+ edge indices + articulation points
Invariant	“low value” hand-wave	Computes correctly	Articulates `low[v] > disc[u]` precisely	+ sketches proof + DFS-tree structure
Scale	Doesn’t think	Hits recursion limit, fixes	Anticipates, writes iterative	+ block-cut tree + dynamic bridges
Generalization	None	“what about vertices?”	Articulation points + condition difference	+ 2-edge-connectivity + Gomory-Hu

12. Level Delta

Mid (L4): Tarjan recursive (works for small input); names algorithm.
Senior (L5): + iterative DFS for scale + correctly handles parent exclusion + states bridge condition precisely.
Staff (L6): + articulation points via ≥ + edge-index parent exclusion for multi-edges + block-cut tree + 2-edge-connected components.
Principal (L7+): + dynamic bridges (Holm-Lichtenberg-Thorup) + Gomory-Hu for k-edge-connectivity + production SRE applications + LP relaxation framing of connectivity.

13. Follow-up Q&A

Q1: Find articulation points (cut vertices) instead. A1: Same DFS framework, change condition to low[v] >= disc[u] for non-root; root is articulation if it has ≥ 2 DFS-children.

Q2: Find ALL 2-edge-connected components. A2: Same DFS but skip bridges during a second DFS to identify components. Or use the block-cut tree.

Q3: Multi-edges? A3: Track parent EDGE INDEX, not parent NODE. Two edges to same node are both legitimate (one tree, one back).

Q4: Edges added/removed dynamically; report bridges after each. A4: Holm-Lichtenberg-Thorup O(log² n) per update; complex implementation.

Q5: Why does iterative DFS need such elaborate state? A5: Recursive DFS implicitly carries for v in adj[u] iteration state via the call stack frame. Iterative DFS must explicitly save (current node, iterator into its neighbor list, child being processed) — otherwise you can’t resume properly after a child returns.

14. Solution Walkthrough

See solution.py:

critical_connections_tarjan — iterative Tarjan; canonical.
critical_connections_tarjan_recursive — recursive variant; only safe for small inputs.
critical_connections_brute — remove each edge, check connectivity (oracle).

15. Beyond the Problem

Principal code review: “Tarjan’s bridge algorithm (1972) and its sibling articulation-point algorithm are the cleanest example of how a single DFS pass, properly instrumented, computes a global structural property of a graph. The disc/low pair is one of those data-structure inventions that feels obvious in retrospect: every node maintains both ‘when did I get here’ and ‘what’s the highest I could go back to.’ From those two scalars you derive bridge-ness, articulation-ness, biconnected components, the block-cut tree, even strongly-connected components (for directed graphs, with a sign flip). In production SRE — fault-tolerance analysis of microservice topologies, redundancy planning, blast-radius computations — these algorithms run on graphs with millions of edges and they finish in linear time. The clarity of ‘low[v] > disc[u] means cut this and the subtree falls off’ is what makes Tarjan one of the field’s most-cited papers. Memorize the seven lines; respect the proof.”

LeetCode Interview — Extreme Coding