警钟撅烂(如果WA #3)
查看原帖
警钟撅烂(如果WA #3)
1174770
xiaoqimingbozai楼主2024/10/11 11:10

在tarjan算法中,有的教材上写了直接检测是否是根,也就只有一个点的强连通分量。要记得出栈,不然如果再次搜到这个点,它的时间戳会影响正常搜索。

void tarjan(int x)
{
	dfn[x]=low[x]=++tot;
	s.push(x);ins[x]=1;
	if(x==root&&g[x].size()==0) {s.pop();ins[x]=0;cnt++;scc[x]=cnt;return;}//这里如果要判是否是根的话,要记得出栈和退出递归
	for(int i=0;i<g[x].size();i++)
	{
		int y=g[x][i];
		if(!dfn[y])
		{
			tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else if(ins[y]) low[x]=min(low[x],dfn[y]);
	}
	if(low[x]==dfn[x])
	{
		int z;cnt++;
		do
		{
			z=s.top();
			s.pop();
			scc[z]=cnt;
			ins[z]=0;
		}while(z!=x);
	}
}
2024/10/11 11:10
加载中...