A divide-and-conquer algorithm for identifying strongly connected components

Strongly connected components of a directed graph can be found in an optimal linear time, by algorithms based on depth first search. Unfortunately, depth first search is difficult to parallelize. We describe two divide--and--conquer algorithms for this problem that have significantly greater potential for parallelization. We show the expected serial runtime of our simpler algorithm to be $O(m\lg n)$, for a graph with $n$vertices and $m$ edges. We then show that the second algorithm has$O(m\lg n)$ worst--case complexity