Tarjan's strongly connected components algorithm is an algorithm in graph theory for finding the strongly connected components (SCCs) of a directed graph.

The basic idea of the algorithm is this: a depth-first search (DFS) begins from an arbitrary start node (and subsequent depth-first searches are conducted on any nodes that have not yet been found).

In other words, it means that in the DFS a node would be only removed from the stack after all its connected paths have been traversed.

At the end of the call that visits v and its descendants, we know whether v itself has a path to any node earlier on the stack.

The connected component rooted at v is then popped from the stack and returned, again preserving the invariant.

It also maintains a value v.lowlink that represents the smallest index of any node on the stack known to be reachable from v through v's DFS subtree, including v itself.

Therefore v must be left on the stack if v.lowlink < v.index, whereas v must be removed as the root of a strongly connected component if v.lowlink == v.index.

[1]: 156 [2] The index variable is the depth-first search node number counter.

The function strongconnect performs a single depth-first search of the graph, finding all successors from the node v, and reporting all strongly connected components of that subgraph.

[3][4] This modified algorithm does not compute the lowlink numbers as Tarjan defined them, but the test v.lowlink = v.index still identifies root nodes of strongly connected components, and therefore the overall algorithm remains valid.

[2] Time Complexity: The Tarjan procedure is called once for each node; the forall statement considers each edge at most once.

The algorithm's running time is therefore linear in the number of edges and nodes in G, i.e.

In order to achieve this complexity, the test for whether w is on the stack should be done in constant time.

In addition, one word is required on each stack frame to hold v and another for the current position in the edge list.

[7] Donald Knuth described Tarjan's SCC algorithm as one of his favorite implementations in the book The Stanford GraphBase.

He also wrote:[9] The data structures that he devised for this problem fit together in an amazingly beautiful way, so that the quantities you need to look at while exploring a directed graph are always magically at your fingertips.