Kosaraju's Algorithm

• Notion: Strongly connected components will also be strongly connected in transposed graph.

vector<vector<int>> adj, radj;
vector<int> timeStamp, scc;
vector<bool> vis;

void dfs(int u) {
    vis[u] = true;
    for (int v : adj[u]) 
        if (!vis[v])
            dfs(v);
    timeStamp.push_back(u);
}

void dfs2(int u, int rep) {
    vis[u] = true;
    scc[u] = rep;
    for (int v : radj[u]) 
        if (!vis[v])
            dfs2(v, rep);
}

void kosaraju() {
    int n = adj.size();
    fill(vis.begin(), vis.end(), false);
    for (int i = 0; i < n; ++i)
        if (!vis[i])
            dfs(i);
    
    fill(vis.begin(), vis.end(), false);
    while(!timeStamp.empty()) {
        int u = timeStamp.back();
        timeStamp.pop_back();
        if (!vis[u])
            dfs2(u, u);
    }
}