社区讨论

关于强连通分量tarjan写法的一个问题

2023/11/12 21:40学术版参与者 4已保存回复 5

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

Rt。在tarjan算法中，枚举点的子节点时，对点的

low

更新有两种情况，一种是新节点，用它的

low

更新，一种是栈内的节点，用

dfn

更新。

求问第二种写法也写用

low

更新是否正确？在我使用tarjan的题目中似乎还没有出现过问题。

也即：

CPP

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]);
}

共 5 条回复，欢迎继续交流。

正在加载回复...