Tarjan算法lowtime概念疑问：为何E/F/G节点的low值不是1？

核心理解偏差 #

你对low值的定义和更新规则存在两处关键遗漏：

Tarjan算法（求解强连通分量场景）中low值的完整定义为：每个节点可直接到达、或通过该节点子树的后向边到达的当前仍在递归栈中的、发现时间（Discovery time）最小的祖先节点对应的时间值。
只有仍在递归栈中的节点才属于和当前节点同一待确认的强连通分量候选集合，已出栈的节点属于其他已完成确认的分量，对应跨分量边不能用于更新low值。

示例中E的low值不为1的原因 #

你产生误解的核心是搞错了low值的更新规则，合法的low值更新仅允许两种操作：

• 遍历到节点u的邻接节点v时，如果v未被访问过：先递归访问v，回溯时执行 low[u] = min(low[u], low[v])
• 遍历到节点u的邻接节点v时，如果v已被访问过、且仍在递归栈中：执行 low[u] = min(low[u], disc[v])，仅允许使用v的发现时间disc[v]，不允许使用v的low值

对应你提到的示例，遍历逻辑如下：

1. A最先被访问，disc[A]=1并入栈，后续依次访问B（disc=2）、C（disc=3），均入栈
2. C的邻接节点E未被访问，递归访问E（disc=4）、F（disc=5）、G（disc=6），依次入栈
3. G的邻接节点C已被访问且在栈中，因此用C的disc值3更新low[G]，得到low[G]=3，此处不能使用C的low值1进行更新
4. 回溯到F，用low[G]=3更新low[F]，得到low[F]=3
5. 回溯到E，用low[F]=3更新low[E]，得到low[E]=3
6. 回溯到C后，C继续处理其他邻接节点，访问到A时A在栈中，用disc[A]=1更新low[C]得到low[C]=1，后续B、D的low值也通过合法规则更新为1
7. 整个遍历过程中，E、F、G没有任何合法路径可以获取到A的disc值1，因此三者的low值最终为3

学习提示 #

理解Tarjan算法时必须绑定递归栈的状态变化逐步骤推导low值更新，不要脱离DFS遍历过程静态通过路径可达性推导结果；同时注意不要混淆求解强连通分量的Tarjan算法和求解割点/桥的Tarjan算法，二者的low值规则存在细微差异，不要混用定义。

内容的提问来源于stack exchange，提问作者priyanka