The Kosaraju-Sharir Algorithm

The Kosaraju-Sharir algorithm finds the strongly connected components of a digraph by requiring two passes of depth-first search. While this algorithm performs more work than Tarjan’s algorithm, it’s elegant in its simple presentation and is easier to understand. Interestingly, despite the extra work, its running time remains asymptotically the same as that of depth-first search, i.e., $O(n+m)$, where $n$ and $m$ are the numbers of vertices and edges, respectively.