Tarjan Strongly Connected Components

Robert Tarjan, 1972

Robert Tarjan’s 1972 algorithm finds all strongly connected components in linear time by maintaining a stack of unfinished vertices and merging back-edges into lowlink values. This museum view animates a six-vertex pattern with one 3-cycle, a bridge-like edge into another component, and a 2-cycle tail. The active DFS vertex glows gold, the explored stack is shown in coral, and assigned components are filled in teal once they pop.