Tarjans

Tarjans refers to Tarjan's algorithm for finding strongly connected components (SCCs) in directed graphs. It identifies maximal sets of nodes in which every vertex is reachable from every other.

It operates by performing a depth-first search. Each vertex gets a discovery time index and a low-link value representing the smallest discovery time reachable from that vertex via tree edges and at most one back edge. When visiting, the algorithm pushes the vertex onto a stack. If the vertex's low-link equals its discovery time, the vertices on the stack up to that vertex form a strongly connected component; they are popped and reported.

The algorithm runs in O(V+E) time and uses O(V) space for the stack and auxiliary data. It is commonly implemented recursively, though non-recursive variants exist to avoid stack overflows.

Tarjan's SCC algorithm is a single-pass alternative to Kosaraju's two-pass algorithm; both partition the graph into SCCs. Tarjan's approach is particularly attractive when a real-time single-pass processing is desired.

Applications include compiler optimizations, program analysis, dependency resolution, circuit design, and network analysis. The method is foundational in graph theory and is often taught alongside other SCC and DFS-based algorithms. The original description appears in Tarjan's 1972 paper "Depth-First Search and Linear Graph Algorithms."