» » Strongly Connected Component (Tarjan)

Strongly Connected Component (Tarjan)

   8:00 PM       

 
vector< int > M[MX];
int color[MX],f[MX],low[MX],ftm,st[MX],top,scc;
bool instack[MX];
void dfs(int u){
	int i,v,sz;
	f[u] = ftm;
	low[u] = ftm;
	ftm++;
	st[top] = u;top++;instack[u] = true;
	sz = M[u].size();
	color[u] = 1;
	for(i=0;i<sz;i++){
		v = M[u][i];
		if(!color[v]){
			dfs(v);
			low[u] = _min(low[u],low[v]);
		}
		else if(instack[v])low[u] = _min(low[u],f[v]);
	}
	if(f[u] == low[u]){
		scc++;
		do{
			v = st[top-1];top--;instack[v] = false;
			printf(" %d",v);
		}while(top && v!=u);
		printf("\n");
	}
}
//n = no.of vertices, m = no.of edges
void tarjanscc(int n){
	int i;
	ftm = top = 0;
	memset(color,0,sizeof(color));
	memset(f,0,sizeof(f));
	memset(low,0,sizeof(low));
	memset(instack,0,sizeof(instack));
	for(i=0;i<n;i++){
		if(!color[i])dfs(i);
	}
	printf("total scc: %d\n",scc);
	for(i=0;i<=n;i++)M[i].clear();
}