Answers for "kosaraju's algorithm"

kosaraju's algorithm

Copy//by YASH DHOKIA
//strongly connected components in graph using kosaraju's algorithm
//implementation of kosaraju's algorithm using adjacency list

#include<bits/stdc++.h>
using namespace std;

void addedge(vector<int> graph[],int u1,int u2) {

	graph[u1].push_back(u2);

}

void DFSrec(vector<int> graph[],vector<bool> &visited,stack<int>&st,int u) {

	visited[u]=true;
	for(int k=0; k<graph[u].size(); k++) {
		if( !visited[graph[u][k]]  ) {
			DFSrec(graph,visited,st,graph[u][k]);
		}
	}
	st.push(u);
}

void DFS(vector<int> tran[],vector<bool> &visited,int x) {

	visited[x]=true;
	cout<<x<<" ";
	for( int k=0; k<tran[x].size(); k++ ) {
		if( !visited[tran[x][k]] ) {
			DFS(tran,visited,tran[x][k]);
		}
	}

}

void kosaraju(vector<int> graph[],int v) {

	vector<bool> visited(v,false);
	stack<int>st;

	for(int i=0; i<v; i++) {
		if( !visited[i] )
			DFSrec(graph,visited,st,i);
	}

	vector<int> tran[v];
	for(int i=0; i<v; i++) {
		visited[i]=false;
		for(int j=0; j<graph[i].size(); j++) {
			tran[graph[i][j]].push_back(i);
		}

	}

	int count=1;
	while(!st.empty()) {
		int x=st.top();
		st.pop();
		if(!visited[x]) {
			cout<<"component " << count++ << ": ";
			DFS(tran,visited,x);
			cout<<endl;
		}
	}

}

int main() {

	int v,e;
	cin>>v>>e;
	vector<int> graph[v];

	for(int i=0; i<e; i++) {
		int u1,u2;
		cin>>u1>>u2;
		addedge(graph,u1,u2);
	}

	kosaraju(graph,v);

	return 0;
}
/*

sample input 1:
5 6
0 1
1 2
1 3
2 1
3 4
4 3

sample input 2:
5 5
0 1
1 2
1 3
2 0
3 4

sample input 3:
11 17
0 2
0 3
1 0
1 10
2 4
3 2
4 3
5 3
5 6
6 4
6 7
7 8
8 5
9 1
10 5
10 8
10 9

*/

kosaraju algorithm

Copy//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;
}

kosaraju algorithm

Copy// Strongly connected components in a graph using Kosaraju's Algorithm

#include<bits/stdc++.h>
using namespace std;
void addedge(vector<int>adj[],int a,int b)
{
    adj[a].push_back(b);
}
void topo(int node,vector<int>adj[],stack<int>&st,vector<int>&visit)
{
    visit[node]=1;
    for(auto i:adj[node])
    {
        if(!visit[i])
        {
            topo(i,adj,st,visit);
        }
    }
    st.push(node);
}
void revdfs(int node,vector<int>&visit,vector<int>transp[])
{
    cout<<node<<" ";
    visit[node]=1;
    for(auto it:transp[node])
    {
        if(!visit[it])
        {
            revdfs(it,visit,transp);
        }
    }
}
int main()
{
    int vertex,edges;
    cout<<"ENTER THE NUMBER OF VERTEX AND EDGES:"<<endl;
    cin>>vertex>>edges;
    vector<int>adj[vertex];
    int a,b;
    cout<<"ENTER THE LINKS:"<<endl;
    for(int i=0;i<edges;i++)
    {
        cin>>a>>b;
        addedge(adj,a,b);
    }
    stack<int>st;
    vector<int>visit(vertex,0);
    for(int i=0;i<vertex;i++)
    {
        if(!visit[i])
        {
            topo(i,adj,st,visit);
        }
    }
    vector<int>transp[vertex];
    for(int i=0;i<vertex;i++)
    {
        visit[i]=0;
        for(auto it:adj[i])
        {
            transp[it].push_back(i);
        }
    }
    while(!st.empty())
    {
        int node =st.top();
        st.pop();
        if(!visit[node])
        {
            cout<<"SCC";
            revdfs(node,visit,transp);
            cout<<endl;
        }
    }
    return 0;
}