Kosaraju Algorithm

Kosaraju-Sharir’s algorithm (also known as Kosaraju’s algorithm) is a linear time algorithm to find the strongly connected components of a directed graph. O(n + m)

Implementation

vector<vector<int>> edges = {{0,1}, {1,0}, {1,2}, {2,3},{3,4},{4,5},{5,2}};

void dfs1(int u, vector<int>& st, vector<bool>& vis1, vector<vector<int>>& adj) {
    vis1[u] = true;
    for(int v : adj[u]) {
        if(!vis1[v])
            dfs1(v,st,vis1,adj);
    }
    st.push_back(u);
}

void dfs2(int u, int rep, vector<bool>& vis2, vector<int>& who, vector<vector<int>>& radj) {
    vis2[u] = true;
    who[u] = rep;
    for(int v : radj[u])
        if(!vis2[v])
            dfs2(v,rep,vis2,who,radj);
}

vector<int> kosaraju(vector<vector<int>>& edges, int n) {
    vector<int> who(n), st;
    vector<vector<int>> adj(n), radj(n);
    vector<bool> vis1(n), vis2(n);

    for(vector<int> e : edges) {
        adj[e[0]].push_back(e[1]);
        radj[e[1]].push_back(e[0]);
    }

    for(int i = 0; i < n; i++) {
        if(!vis1[i]) {
            dfs1(i, st, vis1, adj);
        }
    }

    while(!st.empty()) {
        int u = st.back(); st.pop_back();
        if(!vis2[u])
            dfs2(u,u,vis2,who,radj);
    }

    return who;
}