在这道题的题解中有这样一段代码:
else if(v!=parent[u])
low[u]=min(low[u], dfn[v]);
但是如果不加这句话也能 AC,我对此的理解是:
设无向图 G 中存在两个节点 f 和 s,在 f 的搜索树中 s 为 f 的直接儿子,且在 G 中删除点 f 后 t 在 f 的搜索树中的子树将会成为 G 的一个极大连通子图。
如果不加这句话,则
low(s)=dfn(f)
但是如果加了,则
low(s)=dfn(s)=dfn(f)+1
这时 s 的 dfs
函数退出,程序运行到了 low[f]=min(low[f], dfn[s]);
开始更新 f 的 low 值。
由于 low 值只会越更新越少,即 low(f) 的最大可能值为 dfn(f)。因为 dfn(f)≥low(f)、dfn(s)=dfn(f)+1≥low(f), 所以这两种写法中都不会更新 low(f) 的值,即两种写法都是正确的。
请问我的理解是否正确?