Strongly connected graph(SCC) Kosaraju's algorithm

help
,
1

Can someone please help me!! Thanks in advance
Here I am trying to apply Kosaraju’s algo for SCC

class Solution{
public:
/* Function to find the number of strongly connected components
* using Kosaraju’s algorithm
* V: number of vertices
* adj[]: array of vectors to represent graph
*/
// dfs function which will fill the stack in the reverse order
void dfs(int src, vector adj[] , map<int,bool> &visited, stack &stack){

    vector<int> result;
    visited[src]=true;
   
    
    for(auto itr:adj[src]){
        if(!visited[itr]){
            visited[itr]=true;
            dfs(itr,adj,visited,stack);
        }
    }
    stack.push(src);
    
    
}
int kosaraju(int V, vector<int> adj[]) {
    //code here
     stack<int> s;
     map<int,bool> visited;
     //making visited of adj false
     for(int i=0;i<V;i++){
         visited[i]=false;
     }
     
     dfs(0,adj,visited,s);
     //I have declared another adjacency list to store the reverse  graph 
     vector<int> temp[V];
     for(int i=0;i<V;i++){
         for(auto itr:adj[i]){
             temp[itr].push_back(i);
         }
     }
     
     // this visited_temp is for reverse graph
     map<int,bool> visited_temp;
     for(int i=0;i<V;i++){
         visited_temp[i]=false;
     }
     //count will gives us the count of total number of Stongly connected component(SCC)
     int count =0;
     
     stack<int> t;
     
     while(!s.empty()){   
         
         
        
         int node=s.top();

         s.pop();
         if(!visited_temp[node]){
         dfs(node,temp,visited_temp,t);
         count++;
         }
         
     }
     
     return count;
     
     
     /* Please help, I have already spend around 3,4 hour on this problem, I am getting output expect some testcases.*/
     
}

};

2

You are not filling all the nodes of the graph in the stack, you are only filling the nodes which are connected with node 0. You should loop through all nodes and call dfs for each node.

3

Thank you so so much @lotthbrok Now it is running successfully

4

Here’s a better way to implement Kosaraju’s Algorithm for extracting SCCs:
You can avoid the use of std::map as it adds a log factor to the complexity.

Code For Kosaraju’s Algorithm

1 Like