Day 18 · Week 4

Bridges & Articulation Points

Level 6 · Advanced · 2 hrs: ~45 min theory · ~60 min code · ~15 min notes

🧠 Mental Model

In an undirected graph, a bridge is an edge whose removal disconnects the graph; an articulation point (cut vertex) is a vertex whose removal does. Both are found with the same low-link DFS as Tarjan's SCC — reused for undirected "criticality."

These identify single points of failure: the one cable or one router whose loss splits the network. That framing is exactly how they appear in interviews.

⚙️ Mechanics — low-link, undirected

Same disc (discovery time) and low (lowest reachable disc via the subtree + back-edges) as Day 17, but for undirected DFS we track the parent to skip the edge we came in on.

Bridge condition: tree edge (u, v) (v a child) is a bridge iff low[v] > disc[u] — the subtree at v has no back-edge climbing above u.

Articulation condition: non-root u is a cut vertex iff some child v has low[v] ≥ disc[u]. The root is a cut vertex iff it has ≥ 2 DFS children.

📐 Why the conditions hold

Bridge (low[v] > disc[u]) If no vertex in v's subtree can reach u or an ancestor except through the edge (u,v), then that edge is the sole connection — removing it isolates the subtree. Conversely, a back-edge with low[v] ≤ disc[u] provides an alternate route, so the edge isn't a bridge. ∎

Articulation (low[v] ≥ disc[u]) Here a back-edge may reach u itself but nothing above it. So removing u cuts the subtree off from the rest — u is a cut vertex. The root is special: it has no ancestors, so it only matters if its removal splits ≥2 independent subtrees, i.e. ≥2 DFS children. ∎

The > vs ≥ distinction is the whole subtlety: an articulation point can sit on a cycle (back-edge to itself is fine), a bridge cannot.

📊 Complexity

Metric	Value
Time	O(V + E) — single DFS
Space	O(V) — disc/low arrays + recursion

💻 Reference Implementation (Java)

Finds all bridges. (Articulation points use the ≥ variant + root child-count.)

import java.util.*;

private int[] disc, low;
private int timer;
private List<List<Integer>> bridges;

public List<List<Integer>> findBridges(int n, List<Integer>[] adj) {
    disc = new int[n]; low = new int[n];
    Arrays.fill(disc, -1);
    bridges = new ArrayList<>();
    timer = 0;
    for (int u = 0; u < n; u++) if (disc[u] == -1) dfs(u, -1, adj);
    return bridges;
}

private void dfs(int u, int parent, List<Integer>[] adj) {
    disc[u] = low[u] = timer++;
    for (int v : adj[u]) {
        if (v == parent) continue;         // skip the edge we came from
        if (disc[v] == -1) {              // tree edge
            dfs(v, u, adj);
            low[u] = Math.min(low[u], low[v]);
            if (low[v] > disc[u])          // bridge condition
                bridges.add(Arrays.asList(u, v));
        } else {                          // back edge
            low[u] = Math.min(low[u], disc[v]);
        }
    }
}

Parallel edges: if two edges connect u–v, the "skip parent" trick over-skips. Track the edge id instead of the parent vertex when multi-edges are allowed.

🎭 Problem Variances — criticality in disguise

Disguise / phrasing	What's really asked	Twist to handle
"Critical connections / single point of failure"	Bridges	low[v] > disc[u]
"Critical routers / servers"	Articulation points	low[v] ≥ disc[u]; root needs ≥2 children
"Which links can fail without splitting the network"	Non-bridge edges	Edges on a cycle (2-edge-connected)
"Redundantly connected regions"	2-edge / 2-vertex connected components	Remove bridges → components
"Minimum edges to add to remove all bridges"	Edge-connectivity augmentation	Bridge tree, count leaves → ⌈leaves/2⌉

Directed vs undirected: bridges/articulation points are an undirected notion using low-link. The directed cousin (SCC) was Day 17 — same machinery, different question.

⚠️ Common Pitfalls

> vs ≥ confusion: bridges use strict >; articulation points use ≥. Swapping them is the classic bug.

Root articulation special case: the DFS root is a cut vertex only with ≥2 children — the ≥ rule doesn't apply to it.

Back-edge uses disc, not low: update low[u] = min(low[u], disc[v]) for back-edges.

🎯 Problems

LC 1192 Critical Connections in a Network The canonical bridge-finding problem. Implement the low-link DFS above. Hard

— Articulation points on a custom graph Adapt to the ≥ condition + root child-count; verify on a small hand-drawn graph. Hard

📚 References

Hopcroft & Tarjan (1973) — "Efficient algorithms for graph manipulation," Comm. ACM 16(6). Biconnectivity / articulation points.
Tarjan (1974) — "A note on finding the bridges of a graph," Information Processing Letters 2(6).
CLRS, 3rd ed., §22.3 + Problem 22-2 — DFS edge classification; biconnected components exercise.
cp-algorithms.com — "Finding bridges" and "Finding articulation points."

← Day 17: Tarjan's SCC Day 19: A* + Eulerian →