Tarjan

无向图的割点

先给出几个定理：

• A：一棵树中的所有结点对于任意结点的可达性一致。

记 \(p(u,v)表示u和v可以相互到达\)。
也就是说，如果G是一棵树，那么 \(\forall u,v \in G,\forall k,p(u,k) \iff p(k,u)\)。

• B：一个无向图的DFS树中，对于任意一个非树边\((u,v)\)，\(u,v\)一定有祖先孩子关系。

如果连到了左边的兄弟上，那么DFS树就不会是当前形态了，\((u,v)\)一定是非树边。

同样，如果连到了右边的兄弟上，也是矛盾。（画个图就知道了）

所以，只可能连到祖先或者子树中的孩子上。

• C：点u是割点等价于以u为根的子树G中，存在一个点v，使得v不通过点u，能够到达的所有点都在G中。

正方向：如果不存在，也就是说G里面的x，都可以不通过点u到达G外的点，删去u后，连通性不变，与u是割点矛盾。

反方向：删去点u后，点v此时能到达的点就是原图中不通过点u能到达的点，而点v不能到达G外的点，由定理A，v所在的子树（挂在u上）会形成一个新的连通分量，所以u是割点。

• D：定义 \(low[u]\)（\(u\)的父亲是\(fa\)） 为点u通过一条非树边能够到达的时间戳最小的点的时间戳（和\(dfn[u]\)取个最小值）。那么u是割点等价于\(\exists v \in E(u),low[v]\ge dfn[u]\)，其中 \(E(u)\) 是u的儿子的集合。

正方向：如果u是割点，由C，存在一个v，……。在这个v所属的挂在u上的子树中，由A，所有点的可达性一致，所以找到该树中u的直接儿子s，则s也满足……。从s出发，只经过非树边的路径，若不经过u，所以可到达的所有点的一定在\(G(u)\)中，满足；若经过u，也满足。

反方向：