This algorithm requires a directed graph. Check Settings tab to configure.
Tarjan's SCC Algorithm
Finds strongly connected components using DFS and stack
Time: O(V + E)
Space: O(V)
Use Case: Dependency analysis, social network analysis
Algorithm Execution
Select an algorithm and generate steps to begin visualization
About Tarjan's SCC Algorithm
Tarjan's algorithm finds all strongly connected components (SCCs) of a directed graph in a single depth-first search. A strongly connected component is a maximal set of vertices where every vertex can reach every other by directed paths.
How it works
During one DFS the algorithm assigns each node a discovery index and a low-link value, the smallest index reachable from its subtree using at most one back edge. Nodes are pushed on a stack as they are visited. When a node finishes with a low-link equal to its own index it is the root of an SCC, and the stack is popped down to that node to output the component. Everything happens in O(V + E) time with a single pass.
Applications
SCC decomposition condenses a directed graph into a directed acyclic graph, the first step in solving 2-SAT, analyzing call graphs in compilers, detecting deadlocks, and finding cycles of mutual dependency in package managers or spreadsheets. Tarjan low-link values are a classic hard interview subject.