# Strongly connected graph(SCC) Kosaraju's algorithm

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;

if(!visited[itr]){
visited[itr]=true;
}
}
stack.push(src);

}
int kosaraju(int V, vector<int> adj[]) {
//code here
stack<int> s;
map<int,bool> visited;
for(int i=0;i<V;i++){
visited[i]=false;
}

//I have declared another adjacency list to store the reverse  graph
vector<int> temp[V];
for(int i=0;i<V;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;

}
``````

};

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.

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

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