深入理解图的割点和割边（详细解析）

除了割点还有一种问题是求割边（也称桥），即在一个无向图中删除某条边后，图不再连通。

如何求割边？

只需将求割点的算法修改一个符号就可以。 只需将low[v]>=num[u]改为low[v]>num[u]。

这是为什么呢？

low[v]和num[u]相等则表示还可以回到父亲结点； 而low[v]>num[u]则表示连父亲都回不到了。倘若顶点v不能回到祖先，也没有另外的路能回到父亲，那么 u-v 这条边就是割边。