图论 - xIao_wU 思维磁场 - Just Run And Never Forget I Have A Dream
无向图割点
建议阅读：黄劲松 《无向图的块与圈》
求割点主要理解三个定理：
w定理1：DFS中，e=uv是返祖边，那么要么u是v的祖先，要么u是v的后代子孙。
w定理2：DFS中，e=uv是父子边，且dfn[u] > 1，low[v] ≥ dfn[u]，则u是割点。
w定理3：DFS的根r是割点的充要条件是：至少有2条以r为尾(从r出发)的父子边。
定理1是毋庸置疑的，定理2则是运用定理1来确定u是割点，通俗的表述则为如果 v 是 u 的儿子，而 v 的老祖先也是 u 的后代，则 u 为割点，可以想象，若 u 被去掉，v 的祖先则无法和u的祖先相连接，故u则为割点。定理2有个dfn[u] > 1，则是因为定理三，当dfn[u] == 1时，u为根节点，故需要定理三来补充说明。具体证明过程可以阅读上面的ppt。