关于 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 中存在两个节点 ffss,在 ff 的搜索树中 ssff 的直接儿子,且在 GG 中删除点 ffttff 的搜索树中的子树将会成为 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

这时 ssdfs 函数退出,程序运行到了 low[f]=min(low[f], dfn[s]); 开始更新 fflow\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)+1low(f)\operatorname{dfn}(s) = \operatorname{dfn}(f)+1 \ge \operatorname{low}(f), 所以这两种写法中都不会更新 low(f)\operatorname{low}(f) 的值,即两种写法都是正确的。

请问我的理解是否正确?

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