Strongly connected components

Strongly connected components

Finding strongly connected components - Building condensation graph.

Code

int scc;
vector<int> topo;

void dfs1(int u){
	vst[u]=true;
	for(int v:adj[u]) if(!vst[v]) dfs1(v);
	topo.push_back(u);
}

void dfs2(int u){
	vst[u]=true;
	++scc;
	for(int v:rev[u]) if(!vst[v]) dfs2(v);
}

int main(){
        for(int i=0;i<n;++i) if(!vst[i]) dfs1(i);
	memset(vst,false,sizeof(vst));
	for(int i=n-1;~i;--i) if(!vst[topo[i]]){
		scc=0;
		dfs2(topo[i]);

	}
}