关于强连通分量tarjan写法的一个问题
  • 板块学术版
  • 楼主CZ_7
  • 当前回复5
  • 已保存回复5
  • 发布时间2023/11/12 21:40
  • 上次更新2023/11/13 09:53:04
查看原帖
关于强连通分量tarjan写法的一个问题
348196
CZ_7楼主2023/11/12 21:40

Rt。在tarjan算法中,枚举点的子节点时,对点的 lowlow 更新有两种情况,一种是新节点,用它的 lowlow 更新,一种是栈内的节点,用 dfndfn 更新。

求问第二种写法也写用 lowlow 更新是否正确?在我使用tarjan的题目中似乎还没有出现过问题。

也即:

for(int i:E[x]){
	if(!dfn[i]){tarj(i);low[x]=min(low[x],low[i]);}
	else if(in_stack[i])low[x]=min(low[x],dfn[i]);
}
2023/11/12 21:40
加载中...