关于 Tarjan 的问题
查看原帖
关于 Tarjan 的问题
207996
yzy1Ẽd<ßDream楼主2021/5/10 19:54

在这道题的题解中有这样一段代码:

else if(v!=parent[u])
  low[u]=min(low[u], dfn[v]);

但是如果不加这句话也能 AC,我对此的理解是:

设无向图 GG 中存在两个节点 ff 和 ss,在 ff 的搜索树中 ss 为 ff 的直接儿子,且在 GG 中删除点 ff 后 tt 在 ff 的搜索树中的子树将会成为 GG 的一个极大连通子图。

如果不加这句话,则 low⁡(s)=dfn⁡(f)\operatorname{low}(s)=\operatorname{dfn}(f)

但是如果加了,则

low⁡(s)=dfn⁡(s)=dfn⁡(f)+1\operatorname{low}(s)=\operatorname{dfn}(s)=\operatorname{dfn}(f)+1

这时 ss 的 dfs 函数退出,程序运行到了 low[f]=min(low[f], dfn[s]); 开始更新 ff 的 low\rm low 值。

由于 low\rm low 值只会越更新越少,即 low⁡(f)\operatorname{low}(f) 的最大可能值为 dfn⁡(f)\operatorname{dfn}(f)。因为 dfn⁡(f)≥low⁡(f)\operatorname{dfn}(f) \ge \operatorname{low}(f)、dfn⁡(s)=dfn⁡(f)+1≥low⁡(f)\operatorname{dfn}(s) = \operatorname{dfn}(f)+1 \ge \operatorname{low}(f), 所以这两种写法中都不会更新 low⁡(f)\operatorname{low}(f) 的值,即两种写法都是正确的。

请问我的理解是否正确?

2021/5/10 19:54
加载中...