Skip to main content

Strongly Connected Components - Tarjan

Learn Strongly Connected Components - Tarjan (Graphs, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

Tarjan's Algorithm for Strongly Connected Components Tarjan finds all SCCs in a single DFS . Each vertex gets a discovery time disc and a low-link value low : the smallest discovery time reachable from its subtree using one back edge to a vertex still on the stack. Vertices are kept on a stack. When low[u] == disc[u] , u is the root of an SCC, and everything above it on the stack belongs to that component. Cost: O(V + E) .

More lessons in Graphs