Lab 11 — Bridges & Articulation Points

Goal

Find every bridge (edge whose removal disconnects the graph) and every articulation point (vertex ditto) in a single iterative low-link DFS. This is the undirected twin of Tarjan’s SCC low-link and the core of the connectivity-robustness toolkit: 2-edge-connected components, block-cut trees, single-point-of-failure analysis. Target problem: LC 1192, a real and frequently-asked FAANG Hard. After this lab: LC 1192 iterative in <25 minutes.

Background Concepts

DFS on an undirected graph produces only tree edges and back edges — no cross edges. When you examine edge (u, w) and w is already visited, w is an ancestor or descendant of u; two side-by-side subtrees can never touch, or the edge would have been a tree edge.

Per vertex: disc[v] (discovery time) and low[v] = min disc reachable from v’s subtree via tree edges plus back edges. Then:

• Bridge (tree edge u→v, u parent): low[v] > disc[u]. Strict — v’s subtree has no back edge reaching u or above, so the tree edge is the subtree’s only exit.
• Articulation, non-root u: some child v has low[v] ≥ disc[u]. Non-strict — a back edge reaching exactly u doesn’t help once u itself is removed.
• Articulation, root: ≥ 2 DFS-tree children. The low-link test is vacuous at the root (low[child] ≥ disc[root] always); what matters is whether the root’s children are connected only through it.

Parent skip must be by edge id, not parent vertex. With parallel edges (u, v), (u, v), the second copy is a genuine back edge — the pair forms a 2-cycle and neither is a bridge. Vertex-based skip ignores both copies and misreports a bridge.

These conditions induce two structures: remove all bridges → 2-edge-connected components (contract them: the bridge tree); articulation points + biconnected components → the block-cut tree. Both turn connectivity queries into tree queries.

Relation to SCC (lab-10): same disc/low machinery; there the guard is “on the open-SCC stack,” here it’s “not the parent edge.” Learn them as one pattern with two guards.

Interview Context

LC 1192 (Critical Connections in a Network) is a canonical FAANG Hard — heavily asked at Amazon in “network reliability” clothing. Most candidates who recognize “bridges” still fail on (a) recursion depth at n = 10⁵ in Python and (b) the ≥ vs > distinction between the two conditions. Nailing the iterative version with a clean edge-id skip is a strong senior signal.

Problem Statement (LC 1192)

There are n servers numbered 0..n−1 connected by undirected connections. A critical connection is a connection that, if removed, makes some pair of servers unable to reach each other. Return all critical connections in any order.

Constraints

• 2 ≤ n ≤ 10⁵; n − 1 ≤ connections.length ≤ 10⁵.
• No repeated connections on LC; the implementation below tolerates parallel edges and self-loops anyway — that generality is exactly what the edge-id skip buys.

Clarifying Questions

1. Is the graph connected? (On LC, yes; the code handles forests via the outer loop regardless.)
2. Parallel edges or self-loops possible? (Not on LC; a robust solution treats a parallel pair as a cycle — never a bridge — and ignores self-loops.)
3. Output order? (Any; edges in either endpoint order.)
4. Do you also want the vertices whose removal disconnects the network? (That’s the articulation-point variant — included.)

Examples

criticalConnections(4, [[0,1],[1,2],[2,0],[1,3]]) → [[1,3]]
criticalConnections(2, [[0,1]])                   → [[0,1]]
bridges_and_cuts(2, [(0,1), (0,1)])               → ([], [])        # parallel pair: no bridge
bridges_and_cuts(3, [(0,1), (1,2)])               → ([(0,1),(1,2)], [1])  # path: middle is a cut

Initial Brute Force

For each edge: delete it, run BFS/DFS, check whether the component count grew. Same per vertex for articulation points.

Brute Force Complexity

O(E · (V + E)) for bridges, O(V · (V + E)) for cut vertices. At V = E = 10⁵: ~10¹⁰ operations. TLE — but it is the perfect test oracle for small graphs.

Optimization Path

Every bridge is a tree edge of any DFS tree (a back edge lies on a cycle by construction). So one DFS suffices if each subtree can report “the highest ancestor I can reach without my parent edge” — that is low. Computing low bottom-up during the same DFS gives all bridges and articulation points in O(V + E), one pass, no reverse graph. This is Tarjan’s 1974 low-link technique; the SCC version (lab-10) is the directed sibling.

Final Expected Approach

def bridges_and_cuts(n, edges):
    """One iterative low-link DFS. Returns (bridges, cut_vertices).
    Skips the parent EDGE by id, not the parent vertex — parallel edges
    (u,v),(u,v) must count as a cycle, and vertex-skip would miss that."""
    adj = [[] for _ in range(n)]
    for eid, (u, v) in enumerate(edges):
        adj[u].append((v, eid))
        adj[v].append((u, eid))
    disc = [-1] * n
    low = [0] * n
    children = [0] * n
    is_cut = [False] * n
    bridges = []
    timer = 0
    for s in range(n):
        if disc[s] != -1:
            continue
        stack = [(s, -1, 0)]                     # (vertex, parent edge id, next child)
        while stack:
            v, pe, i = stack[-1]
            if i == 0:                           # first visit
                disc[v] = low[v] = timer
                timer += 1
            if i < len(adj[v]):
                stack[-1] = (v, pe, i + 1)
                w, eid = adj[v][i]
                if eid == pe:                    # the one tree edge we came in on
                    continue
                if disc[w] != -1:                # back edge
                    low[v] = min(low[v], disc[w])
                else:
                    stack.append((w, eid, 0))    # tree edge
            else:                                # v finished: report to parent
                stack.pop()
                if stack:
                    pv = stack[-1][0]
                    low[pv] = min(low[pv], low[v])
                    children[pv] += 1
                    if low[v] > disc[pv]:        # bridge condition
                        bridges.append(edges[pe])
                    if stack[-1][1] != -1 and low[v] >= disc[pv]:
                        is_cut[pv] = True        # non-root articulation
        if children[s] >= 2:                     # root articulation
            is_cut[s] = True
    return bridges, [v for v in range(n) if is_cut[v]]

def criticalConnections(n, connections):        # LC 1192
    return bridges_and_cuts(n, connections)[0]

Data Structures Used

• Adjacency lists of (neighbor, edge_id) pairs — the id is what makes parallel edges and the parent skip correct.
• disc, low, children int arrays; is_cut boolean array.
• One explicit frame stack of (vertex, parent_edge_id, next_child_index) — the recursion replacement.

Correctness Argument

No cross edges: if (u, w) is examined with w visited and w is neither ancestor nor descendant of u, then w’s subtree finished before u was discovered — but DFS would have traversed (u, w) from w’s side then, making it a tree edge. Contradiction. So every non-tree edge’s disc[w] is an ancestor’s (or a finished descendant’s, whose larger disc is harmless in the min).

Bridge ⇔ low[v] > disc[u]: (⇐) every path out of subtree(v) uses either the tree edge (u,v) or a back edge from the subtree; low[v] > disc[u] says no back edge reaches u or above, so removing (u,v) isolates the subtree. (⇒) contrapositive: a back edge to disc ≤ disc[u] gives a second edge-disjoint route, so (u,v) lies on a cycle — not a bridge.

Articulation: removing non-root u disconnects child subtree v from the rest iff no back edge from subtree(v) climbs strictly above u — reaching u exactly is useless once u is gone, hence ≥. The root has no “rest above”; it separates its children iff it has ≥ 2 of them in the tree (each child subtree explored fully before the next starts, so two children ⇒ no path between them avoiding the root).

Once-per-edge reporting: a bridge is emitted only when its child endpoint’s frame pops — exactly once per tree edge.

Complexity

Implementation Requirements

• Iterative DFS — LC 1192’s n = 10⁵ path graph is a 10⁵-deep recursion; Python dies even with a raised limit.
• Parent skip by edge id (eid == pe), never by vertex.
• The i == 0 gate: frames re-enter once per child; discovery bookkeeping must run once.
• low[parent] = min(low[parent], low[child]) and the bridge/cut checks happen at child-pop time, not push time.
• Outer loop over all vertices: handles disconnected inputs and forests.

Tests

• LC example → [[1,3]]; two-vertex single edge → that edge; triangle → no bridges, no cuts.
• Parallel pair (0,1)×2 → no bridges, no cuts. Self-loop (0,0) → tolerated, nothing reported.
• Path 0–1–2 → both edges bridges, vertex 1 the only cut.
• 400 random graphs (n ≤ 10, up to 2n edges, duplicates allowed) vs the deletion brute force: bridge iff removing the edge increases component count; cut iff removing the vertex does. Exact match on both outputs.
• Scale: 10⁵-vertex path — all n−1 edges bridges, n−2 cuts, no recursion error.

Follow-up Questions

• Why must the parent edge id be skipped rather than the parent vertex? → With parallel edges (u,v),(u,v), the two copies form a cycle: neither is a bridge. Vertex-skip discards both copies from v’s scan, so subtree(v) shows no back edge and (u,v) is misreported as a bridge. Edge-id skip discards only the one tree edge; the twin correctly updates low[v] = disc[u]. Any multigraph input (and many real datasets) needs this.
• What is a block-cut tree and what does it answer? → Nodes = biconnected components (blocks) + cut vertices; a cut vertex connects to each block containing it. It’s a tree. “Does every a→b path pass through v?” ⇔ v is a cut vertex lying on the block-tree path between a’s and b’s blocks. Turns separation queries into LCA/path queries.
• “Add the fewest edges to make the network 2-edge-connected”? → Contract 2-edge-connected components → the bridge tree (bridges become tree edges). Answer: ⌈leaves/2⌉ — pair up leaves across the tree. Classic follow-up to LC 1192.
• Edges are being deleted online — maintain bridges dynamically? → Genuinely hard. Fully dynamic connectivity is Holm–de Lichtenberg–Thorup O(log² n) amortized; deletions-only usually go offline: divide-and-conquer over the query timeline with a rollback DSU. Name these; don’t attempt them in 45 minutes.
• Is there a directed analogue? → Yes: strong bridges and strong articulation points (removal breaks strong connectivity), computable via dominator trees of G and G-reversed (Italiano et al.). Rarely asked — knowing they exist and that “run undirected low-link” is wrong on digraphs is the whole point.

Product Extension

Datacenter fault analysis: model switches/routers as vertices, links as edges; bridges are the links whose failure partitions the network, articulation points the routers. Run after every topology change; feed the bridge tree into capacity planning (“which single link additions remove all bridges?” = the ⌈leaves/2⌉ computation). The same audit applies to microservice call graphs and power grids — “critical connection” is a literal SRE term here.

Language/Runtime Follow-ups

• Python: iterative mandatory (C-stack segfault beats sys.setrecursionlimit on 10⁵-deep paths). Tuples-in-list frames are fastest; avoid per-frame objects.
• C++: recursive is idiomatic and survives ~10⁵–10⁶ depth on an 8 MB stack; vector<pair<int,int>> adjacency.
• Java: default thread stack dies near 10⁴ frames — the new Thread(null, task, "dfs", 1 << 26) trick or an explicit stack.
• Go: goroutine stacks grow on demand; recursive DFS is safe.
• JS/TS: ~10⁴-frame engine cap; iterative required. LC’s JS judge on 1192 punishes recursive solutions with stack overflow.

Common Bugs

1. Parent-vertex skip: the headline bug — correct on simple graphs, silently wrong on multigraphs; a parallel pair gets reported as a bridge. Skip by edge id.
2. > vs ≥ swapped: bridges need strict low[v] > disc[u]; articulation needs low[v] ≥ disc[u]. Swapping makes cycle edges bridges or misses cut vertices whose subtree loops back exactly to them.
3. Root handled by the low-link test: low[child] ≥ disc[root] is always true — every root with one child gets flagged. The root needs the ≥ 2-tree-children rule.
4. Counting children per examined edge: incrementing children when scanning edges (rather than when a child frame pops) counts back edges as children — the root of a triangle gets flagged.
5. Missing low propagation at pop: in iterative form, forgetting low[parent] = min(low[parent], low[child]) makes every tree edge look like a bridge.
6. Bridge appended from both directions: emitting on the scan of each endpoint duplicates every bridge; emit only at child-pop.

Debugging Strategy

Property-check the output before reading the code: for each reported bridge, delete it and assert the component count grows; assert no unreported edge does the same (O(E²) but fine at test scale) — this instantly classifies false positives vs false negatives. False positives on graphs with parallel edges → the skip is vertex-based. False positives everywhere → missing low propagation or swapped ≥/>. Then hand-trace the 4-node LC example printing (v, disc[v], low[v]) at each pop: expected low = [0,0,0,3], and only edge (1,3) satisfies low[3] > disc[1].

Mastery Criteria

• Solved LC 1192 with an iterative DFS, clean first submission, in <25 minutes.
• Stated all three conditions (bridge, non-root cut, root cut) with correct >/≥ in <1 minute.
• Explained why the parent edge, not vertex, is skipped — with the parallel-edge counterexample — in <1 minute.
• Derived the bridge condition from the no-cross-edges lemma on a whiteboard.
• Answered the bridge-tree follow-up (⌈leaves/2⌉ edge additions) without prompting.
• Mapped this lab onto lab-10: same low-link, different guard (parent edge vs SCC stack).