割点和桥

定义

在一个无向图中，如果有一个顶点集合，删除这个顶点集合以及这个集合中所有顶点相关联的边以后，图的连通分量增多，就称这个点集为割点集合。

如果某个割点集合只含有一个顶点 \(X\)（也即 \(\{X\}\) 是一个割点集合），那么 \(X\) 称为一个割点（割顶）。

在一个无向图中，若删去某条边后无向图的连通分量增加，则称这条边为这张图的割边（桥）。

前置算法：Tarjan 算法。

在 DFS 树中，如果以某个点为根的子树中没有向外（不包括根的父节点）的边（返祖边），那么它的父节点就是一个割点。在算法中表现为 dfn[u]<=low[v] （注意：可以取等）。

如下图：

割点示意图

特别注意：当根节点只有一个子树时，根节点不是割点。

在 DFS 树中，如果以某个点为根的子树中没有向外的边（返祖边），那么从它到它的父节点的边就是一条割边。在算法中表现为 dfn[u]<low[v] （注意：不能取等）。

例题：Code

注：部分资料来源于百度百科

参考资料：

【R9OI】Tarjan 算法及其应用（https://www.bilibili.com/video/BV1ya411M7Tc）