Function kosaraju

CPP/graph_tree/Kosaraju Algorithm.cpp:35–83

Function to find number of strongly connected components in the graph.

	
//Function to find number of strongly connected components in the graph.
int kosaraju(int V, vector<int> adj[])
{
    int i,j;
    
    stack<int> stk;
    
    vector<int> result;
    vector<bool> visited(V,false);
    
    for(i=0;i<V;i++)
    {
        if(!visited[i])
        {
            dfs(i,adj,visited,stk);
        }
    }
    
    while(!stk.empty())
    {
        result.push_back(stk.top());
        stk.pop();
    }
    
    vector<int> g[V];
    
    for(i=0;i<V;i++)
    {
        for(auto x: adj[i])
        {
            g[x].push_back(i);
        }
    }
    
    for(i=0;i<V;i++) visited[i]=false;
    
    int cnt=0;
    
    for(i=0;i<V;i++)
    {
        int node=result[i];
        if(!visited[node])
        {
            cnt++;
            dfsRec(node,g,visited);
        }
    }
    
    return cnt;
}