An articulation point (cut vertex) is a vertex whose removal increases the number of connected components — the graph falls apart into two or more pieces. In a network these are single points of failure: cut the link through that node and traffic stops flowing. Tarjan’s algorithm finds all of them in a single DFS, in O(V+E).

How It Works

1. Run DFS from a root, numbering every vertex with a discovery time (disc) — the order it was first visited.
2. Track low-link values — low[v] is the smallest discovery time reachable from v by following its subtree and then one back edge upward.
3. Non-root test: a non-root vertex u is an articulation point if it has a child v in the DFS tree with low[v] >= disc[u] — meaning v’s whole subtree stays below u; removing u strands it.
4. Root rule: the DFS root is an articulation point if it has two or more children in the DFS tree.

Key Insight

The condition low[v] >= disc[u] is a reachability certificate. When DFS finishes a child v of u, low[v] tells you the earliest vertex v’s subtree can reach without passing through u. If that’s disc[u] or later, then nothing in v’s subtree has an escape route above u — u is the only bridge, so it’s a cut vertex. Back edges are what make low smaller and clear u of suspicion.

Worked Example

Run the visualizer on the undirected sample graph. Watch the disc/low table on the right panel update as DFS descends:

• The first vertex gets disc = low = 1.
• Each tree edge (first visit) sets disc[v] = low[v] = ++time and pushes deeper.
• Each back edge to an already-visited ancestor tightens low: low[u] = min(low[u], disc[v]).
• When a subtree finishes, low propagates up to its parent, and the low[child] >= disc[parent] test fires immediately.

A vertex whose subtree has no back edge over it turns rose in the visualization — that’s an articulation point. The root appears as a cut vertex only if DFS produced multiple children from it.

Edge Cases & Pitfalls

• Root special case: the root rule differs — a root with one DFS child is not an articulation point even though low[child] >= disc[root] would suggest it.
• Back edges vs tree edges: only back edges tighten low; cross edges (to already-done vertices that aren’t ancestors) don’t, so check v != parent[u].
• Disconnected graphs: run DFS from every unvisited vertex — articulation points are computed per component.
• Bridges: an edge whose removal increases components is a bridge; the same DFS with low[v] > disc[u] finds them.
• >= vs >: low[v] >= disc[u] detects articulation points; low[v] > disc[u] detects bridges — off-by-one matters.

Applications

• Network reliability — identifying single points of failure in topologies
• Circuit analysis — finding components that depend on a single node
• Critical infrastructure — router and road-network vulnerability assessment

Practice Trajectory

1. Trace the DFS and record disc/low for each node by hand.
2. Identify every back edge and confirm each one lowers its ancestor’s low.
3. Apply the low[child] >= disc[u] test to confirm each rose node.
4. Re-run on a graph where the root has two children and confirm the root rule.
5. Adapt the algorithm to find bridges and note the > vs >= change.