Problem: Input: a Digraph(G) (Digraph = directed graph) Output: a list of lists of Vertices(G) s.t. each list is a strongly directed component of G StronglyDirectedComponents(G) L := TopoSort(G) G' := G where I reverse all edges /* another DFS visit of G' */ out := EmptyList() for each v in L // I visit according to L, not Vertices(G) if not(marked(v)) then S := EmptyList() Visit(G',v,S) push(out,S) return out Visit(G',v,S) // same used in TopoSort etc. mark(v) for each w in AdjSet(G',v) if not(marked(v)) then Visit(G',w,S) push(S,w) Main ideas: 1) TopoSort clusters together the nodes in the strongly connected component and topologically sorts the components 2) The topological order for the reversed graph lists first the components at the "bottom" of the DAG, i.e. those with incoming edges only; the ones that can reach it are listed later 3) Thus, every call to Visit in the algorithm above can just reach the nodes in the connected components of v (plus the ones in the connected components "below", but those are already marked)