Kosaraju - Implementation

Here is Kosaraju:

function dfs1(v, adj, vis, st):
    vis[v] = true
    for u in adj[v]:
        if not vis[u]:
            dfs1(u, adj, vis, st)
    st.push(v)

function dfs2(v, radj, vis, comp):
    vis[v] = true
    scc[v] = comp
    for u in radj[v]:
        if not vis[u]:
            dfs2(u, radj, vis, comp)

Build transpose graph, run dfs1 on all nodes, then run dfs2 in stack order.

This runs in $O(V + E)$ time and uses $O(V)$ space.