Kosaraju and Sharir

For marking strong components.

Pseudo-code

\begin{algorithm}
\caption{Kosaraju and Sharir}
\begin{algorithmic}
	\Procedure{PushPostRevDFS}{$v, S$}
		\State \Call{mark}{$v$}
        \ForAll{edges $u \to v \in E$}
			\If{$u$ is unmarked}
		        \State \Call{PushPostRevDFS}{$u, S$}
            \EndIf
        \EndFor
        \State $S.$\Call{push}{$v$}
    \EndProcedure
    \Procedure{LabelOneDFS}{$v, r$}
	    \State $v.root \gets r$
	    \ForAll{edges $v \to w \in E$}
		    \If{$w.root = none$}
			    \State \Call{LabelOneDFS}{$w, r$}
            \EndIf
        \EndFor
    \EndProcedure
	\Procedure{KosarajuSharir}{$G$}
		\State $S \gets stack(\emptyset)$
		\ForAll{vertices $v \in V$}
			\State \Call{unmark}{$v$}
			\State $v.root \gets none$
        \EndFor
        \State \\
        \ForAll{vertices $v \in V$}\Comment{Phase 1}
	        \If{$v$ is unmarked}
				\State \Call{PushPostRevDFS}{$v, S$}
            \EndIf
        \EndFor
        \State \\
        \While{$S$ is not empty}\Comment{Phase 2}
	        \State $v \gets S.$\Call{pop}{}
	        \If{$v.root = none$}
		        \State \Call{LabelOneDFS}{$v, v$}
            \EndIf
        \EndWhile
    \EndProcedure
\end{algorithmic}
\end{algorithm}

Runtime

$$O(|V|+|E|)$$