2408727188GHR @ 2023-08-24 21:59:30
在这段代码中，无论是low[now] = std::min(low[now], low[nxt]);还是low[now] = std::min(low[now], dfn[nxt]); 都可以AC
for(auto [nxt, ed]: g[now]) {
if(ed == last_edge)
continue;
if(dfn[nxt] == 0) {
dfs(nxt, ed);
low[now] = std::min(low[now], low[nxt]);
} else {//不存在横叉边，所以不需要判断in_stk
low[now] = std::min(low[now], low[nxt]);
}
}by Edgebright @ 2023-08-24 22:35:02
你会发现两种方法求出来每个点的low其实是不一样的。都能ac是因为这两种方法更新low判定桥的情况是一样的。low[now] = std::min(low[now], dfn[nxt])表示：在求桥的时候，我们定义low为某点经过一些树边（可以为0）和至多1条非树边（不是直接子到父的反边）能到达的点的最小dfn。这中判定的正确性是基于：一条非树边逃不出去，那不管多少条都不行。这是因为：考虑走的第一条非树边。如果它指向子树，那这条边不需要走非树边，直接从树边过来。如果它指向外面，dfn一定更小，直接逃出去了。所以一条不行，多少条都不行。
low[now] = std::min(low[now], low[nxt]);表示我们定义low为经过任意条树边和非树边能到达的dfn最小节点。这更简单明了，出不去就是出不去。
by Edgebright @ 2023-08-24 22:37:19
总结：不同的更新方法对应了我们对low不同的定义，而这两种定义方法恰好在判断桥上是相同的。实际上这两种定义方法对于判强联通分量也是相同的。
我刚刚语言过于急促可能没说人话，我分享一下我以前的博客。不过那个是基于强连通分量写的，虽然差不多。博客