Untitled

mail@pastecode.io avatarunknown
plain_text
a month ago
1.3 kB
2
Indexable
Never
#include<unordered_map>
#include<vector>
#include<list>
#include<stack>
//directed unweighted graph
//1st step
void dfs(int node, vector<bool>&vis, stack<int>&s, unordered_map<int,list<int>> &adjlist){
	vis[node]=true;
	for(auto nbr:adjlist[node]){
		if(!vis[nbr]){
			dfs(nbr,vis,s,adjlist);
		}
	}
	s.push(node);
}

void revdfs(int node,vector<bool>&vis, unordered_map<int,list<int>> &transpose){
	vis[node]=true;
	for(auto nbr:transpose[node]){
		if(!vis[nbr]){
			revdfs(nbr,vis,transpose);
		}
	}
}

int stronglyConnectedComponents(int v, vector<vector<int>> &edges)
{
	unordered_map<int,list<int>> adjlist;
	for(int i=0;i<edges.size();i++){
		int u=edges[i][0];
		int v=edges[i][1];
		adjlist[u].push_back(v);
	}
	stack<int> s;
	vector<bool> vis(v,false);
	for(int i=0;i<v;i++){
		if(!vis[i]) dfs(i,vis,s,adjlist);
	}

	//transpose graph 2nd step
	unordered_map<int,list<int>> transpose;
	for(int i=0;i<v;i++){
		vis[i]=0;
		for(auto nbr:adjlist[i]){
			transpose[nbr].push_back(i);
		}
	}

	//traverse with stack
	int count=0;
	while(!s.empty()){
		int top=s.top();
	    s.pop();
		if(!vis[top]) {
			count++; //here the count is inceremted not inside revdfs
			revdfs(top,vis,transpose);
		}
	}
	return count;
}
//