Tarjan疑问求大佬解答

yuancailiao @ 2024-11-28 22:56:12

by mxt8002 @ 2024-11-28 23:05:41

求强联通分量应该是可以用 low 来更新的。但是求割点就会有问题。

by xyz105 @ 2024-11-29 10:44:20

@yuancailiao low[u] 的定义是从点 u 出发，不经过任何从祖先走过来的边能走到的 DFS 树上的祖先的最小 dfn 编号。

因此，如果 v 已被访问且在栈中，说明 v 是满足条件的祖先，于是有 low[u] = min(dfn[v], low[u])。

作为对比，如果 v 没被访问，那么继续对 v 做 tarjan，这个时候才有 low[u] = min(low[v], low[u])。

如有异议欢迎指出。

by xyz105 @ 2024-11-29 10:46:45

@mxt8002 哥们不要误导人好不好。谁说求 SCC 就不能用 dfn 更新 low 值了。

by yuancailiao @ 2024-11-29 13:35:19

@xyz105 所以min(low[v],low[u])应该是没问题的吗？ 用dfn更新会不会使low更新的不是最小编号呢？

by xyz105 @ 2024-11-29 14:32:11

@yuancailiao 哥们自己去打 Tarjan 板子就知道什么时候该用 dfn 更新什么时候用 low 了。