kosaraju algorithm
//By Soumyadeep Ghosh @soumyadepp on Instagram
//Kosaraju's algorithm for Strongly Connected Components
/*Kosaraju's algorithm for Finding the number of Strongly Connected Components of a graph works on the fact
that on transposing a graph, i.e reversing all it's edges, the strongly connected components are unaffected.
This works in three steps:
1)Build a stack for the nodes using dfs. The node to finish the dfs latest shall be on top.
2)Transpose the graph
3)Perform dfs on the elements of the stack starting from top if it is unvisited and keep popping.
4)The number of SCC is merely the number of times DFS was called.
*/
#include <bits/stdc++.h>
using namespace std;
//dfs for building the initial stack
void dfsHelper(vector<int>*adj,int src,bool visited[],stack<int>&st)
{
visited[src] = true;
for(int i = 0 ; i < adj[src].size(); i++)
{
if(!visited[adj[src][i]])
{
dfsHelper(adj,adj[src][i],visited,st);
}
}
st.push(src);
}
//dfs for finding connected components of transposed graph
void dfs(vector<int>*adj,int src,bool visited[])
{
visited[src] = true;
for(int i = 0 ; i < adj[src].size();i++)
{
if(!visited[adj[src][i]])
{
dfs(adj,adj[src][i],visited);
}
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
vector<int>*adj;
stack<int>helperStack;
bool *visited;
int StronglyConnectedComponents = 0;
int n,e;
cin>>n>>e;
visited = new bool[n + 1];
adj = new vector<int>[n + 1];
for(int i = 0 ; i < e ; i++)
{
int u,v;
cin>>u>>v;
adj[u].push_back(v);
}
//mark all the nodes as unvisited
for(int i = 0 ; i <= n ; i++)
{
visited[i] = false;
}
//call dfs for the initial graph
dfsHelper(adj,1,visited,helperStack);
//make another adjacency list to store the transpose of the graph
vector<int>reversed[n+1];
for(int i = 1; i <= n; i++)
{
for(int j = 0 ; j < adj[i].size(); j++)
{
reversed[adj[i][j]].push_back(i);
}
}
//mark all the nodes as unvisited
for(int i = 0 ; i <= n ; i++)
{
visited[i] = false;
}
//starting from the top of the stack go visit every node and perform dfs on it, if it is not visited
//The total number of strongly connected components will be the number of times dfs is called.
while(!helperStack.empty())
{
int k = helperStack.top();
if(!visited[k])
{
dfs(reversed,k,visited);
StronglyConnectedComponents++;
}
helperStack.pop();
}
cout<<"The number of strongly connected Components are "<<StronglyConnectedComponents<<endl;
}
return 0;
}
Are there any code examples left?
New code examples in category C++