关于Tarjan
  • 板块学术版
  • 楼主lzqy_
  • 当前回复3
  • 已保存回复3
  • 发布时间2021/7/19 14:52
  • 上次更新2023/11/4 14:11:11
查看原帖
关于Tarjan
288716
lzqy_楼主2021/7/19 14:52

rt,这是一个普通的强连通分量代码:

void tarjan(int x)
{
	dfn[x]=low[x]=++cnt,st[++top]=x,k[x]=1;
	for(register int i=0;i<v[x].size();i++)
		if(!dfn[v[x][i]]) tarjan(v[x][i]),low[x]=min(low[x],low[v[x][i]]);
		else if(k[v[x][i]]) low[x]=min(low[x],dfn[v[x][i]]);
	if(dfn[x]==low[x])
	{
		ans++;
		while(st[top+1]!=x)
			k[st[top]]=0,col[st[top--]]=ans;
	} 
}

在循环中,如果点 v[x][i]v[x][i] 所在的强连通分量已经处理完,就不用它来更新 low[x]low[x]。可是 low[x]low[x] 的定义不是 xx 所能到达的最远节点吗,不知道是哪里理解出了问题,求解答!

2021/7/19 14:52
加载中...