Strongly Connected Components
Problem Description
The strongly connected components or diconnected components of an arbitrary
directed graph form a partition into subgraphs that are themselves strongly connected.
Bounds Chart
Step Chart
Improvement Table
Complexity Classes  Algorithm Paper Links  Lower Bounds Paper Links 

Exp/Factorial  
Polynomial > 3  
Cubic  
Quadratic  Paul Purdom; 1970 (1970)  
nlogn  Munro’s algorithm (1971)  
Linear  Kosaraju's algorithm (1978)
Tarjan's strongly connected components algorithm (1972) Pathbased strong components algorithm; Dikjstra (1976) 

logn 