Articulation points & bridges
O(V + E)In an undirected graph, an articulation point (cut vertex) is a vertex whose removal disconnects the graph, and a bridge is an edge with the same property. They mark the single points of failure in a network. Tarjan's algorithm finds them all in one DFS. As it visits each vertex it stamps a discovery time disc[u], and computes low[u]: the earliest-discovered vertex reachable from u's subtree using tree edges plus at most one back edge. The key test, for a tree edge from u down to v: if low[v] ≥ disc[u], then v's subtree has no back edge climbing above u, so removing u would strand it — u is a cut vertex. If the inequality is strict (low[v] > disc[u]), the edge u–v is a bridge. The DFS root is special: it's a cut vertex only if it has two or more children. It runs in O(V + E). Cut vertices appear in red and bridges are highlighted.
How it works
- DFS the graph, numbering vertices in visit order (disc).
- Track low[u]: the earliest vertex reachable from u's subtree.
- A child whose subtree can't climb above u (low[v] ≥ disc[u]) makes u a cut vertex.
- If it can't even reach u (low[v] > disc[u]), the connecting edge is a bridge.
Pseudocode
1articulation(graph): # Tarjan, O(V + E)2 DFS, numbering vertices disc[u] in visit order3 low[u] = lowest disc reachable from u’s subtree4 (via tree edges + one back edge)5 for a tree edge u→v:6 if low[v] ≥ disc[u] and u is not the root: u is a cut vertex7 if low[v] > disc[u]: edge u–v is a bridge8 root is a cut vertex iff it has ≥ 2 DFS children