Tarjan

To mark strong components.

Pseudo-code

\begin{algorithm}
\caption{Tarjan}
\begin{algorithmic}
	\Function{TarjanDFS}{$v, S, E, clock$}
		\State \Call{mark}{$v$}
		\State $clock \gets clock + 1$
		\State $v.pre \gets clock$
		\State $v.low \gets clock$
		\State $S.$\Call{push}{$v$}
		\ForAll{edges $v \to w \in E$}
			\If{$w$ is unmarked}
				\State $clock \gets$ \Call{TarjanDFS}{$w, S, E, clock$}
				\State $v.low \gets$ \Call{min}{$v.low, w.low$}
			\Else
				\If{$w.root = none$}
					\State $v.low \gets$ \Call{min}{$v.low, w.pre$}
                \EndIf
            \EndIf
        \EndFor
        \If{$v.low = v.pre$}
	        \State \textbf{do}
		        \State $\>\>\>\>\>$ $w \gets S.$\Call{pop}{}
		        \State $\>\>\>\>\>$ $w.root \gets v$
		    \State \textbf{while} $w \neq v$
        \EndIf
        \Return $clock$
    \EndFunction
    \State \\
    \Function{Tarjan}{$G$}
	    \State $clock \gets 0$
	    \State $S \gets stack(\emptyset)$
	    \ForAll{vertices $v \in G.V$}
		    \State \Call{unmark}{$v$}
		    \State $v.root \gets none$
        \EndFor
        \ForAll{vertices $v$}
	        \If{$v$ is unmarked}
		        \State $clock \gets$ \Call{TarjanDFS}{$v, S, G.E, clock$}
            \EndIf
        \EndFor
    \EndFunction
\end{algorithmic}
\end{algorithm}

Runtime

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