有向图连通性tarjan

• 有向图连通性tarjan

int nc[M],vc[M],hc[N],cc;
int s[N],to=1,in[N],c[N];
vector<int> sc[N];
int dx,ct;
int df[N],lo[N];
void adc(int x,int y)
{
	nc[++cc]=hc[x];hc[x]=cc;v[cc]=y;
}
void tar(int no)
{
	df[no]=lo[no]=++dx;
	s[to++]=no;in[no]=1;
	for(int i=h[no];i;i=nx[i])
	{
		if(!dfn[v[i]])
		{
			tar(v[i]);
			lo[no]=min(lo[no],lo[v[i]]);
		}
		else if(in[v[i]])
			lo[no]=min(lo[no],df[v[i]]);
	}
	if(df[no]==lo[no])
	{
		++ct;
		while(s[to-1]!=x)
		{
			c[s[to-1]]=ct;
			in[s[to-1]]=0;
			--to;
		}
	}
}
void bc()
{
	for(int i=1;i<=n;i++)
	{
		for(int p=h[i]];p;p=nx[p])
		{
			if(c[v[i]]!=c[i])adc(c[v[i]],v[i]);
		}
	}
}

有向图连通性tarjan

原文：https://www.cnblogs.com/hangzz/p/13325448.html