articulation points

In a network, some nodes are quietly load-bearing: pull them out and the whole thing splits into disconnected pieces. An articulation point (or cut vertex) of an undirected graph is exactly such a node — a vertex whose removal, along with its edges, increases the number of connected components, breaking a once-connected region into two or more. Spotting them tells you where a network is fragile: a single point of failure whose loss disconnects parts that could previously reach each other.

There is a fast way to find all of them in one DFS, using the same low-link idea as Tarjan's SCC method. Run DFS, giving each vertex a discovery time disc(u), and compute low(u): the earliest discovery time reachable from u's DFS subtree using tree edges plus at most one back edge. Now the test. The DFS root is an articulation point exactly when it has two or more children in the DFS tree (its removal severs subtrees that had no other way to connect). A non-root vertex u is an articulation point exactly when it has a child v in the DFS tree with low(v) >= disc(u): this says v's whole subtree has no back edge climbing above u, so u is the only bridge between that subtree and the rest — remove u and the subtree falls off. The reasoning is that a back edge reaching above u would give the subtree an alternate escape route, and low(v) records precisely the highest such escape; if even the best escape does not get above u, u is essential.

This runs in O(n + m), one traversal, and it pinpoints every single point of failure in a network — vital for assessing reliability of communication, transport, and power grids, and for breaking a graph into its robust biconnected pieces. Two honest cautions. The root rule is special and easy to forget: the root is a cut vertex only if it has two or more DFS-tree children, not based on its low value. And articulation points are about removing a vertex; the closely related notion of a bridge is about removing an edge — they are different, though both come from the same low-link machinery, and a graph can have a cut vertex with no bridges or vice versa.