割点

$dfn$与$low$:

对图深搜时，每一个节点只访问一次，被访问过的节点与边构成搜索树

时间戳 $dfn_u$: 节点 $u$ 第一次被访问的顺序

追溯值 $low_u$: 从节点 $u$ 出发，所能访问到的最早时间戳

int dfn[N], low[N];

割点的定义

对于一个无向图,若把一个点删除后,连通块的个数增加了,那么这个点就是割点

割点判定法则

1. 若 $u$ 不是根节点,
   • 当搜索树上存在 $u$ 的一个子节点 $v$,满足 $low_v \ge dfn_u$,那么 $u$ 就是割点
2. 若 $u$ 是根节点,
   • 当搜索树上存在至少两个子节点 $v_1$、$v_2$,满足上述条件,那么 $u$ 就是割点

证明

若 $low_v \ge dfn_u$,

• 说明从 $v$ 出发,在不通过 $u$ 点的前提下,不管走哪条边,都无法到达比u更早访问的节点
• 故删除 $u$ 点后,以 $v$ 为根的子树 $subtree(v)$ 也就断开了。即环顶的点割得掉

反之,若 $low_v \lt dfn_v$,

• 则说明 $v$ 能绕行其他边到达比 $u$ 更早访问的节点, $u$ 就不是割点了。即环内的点割不掉

void tarjan(int u) {
    dfn[u] = low[u] = ++tot; // 入u时,盖戳
    int son = 0;
    
    for (int v : a[u]) {
        if (!dfn[v]) { // 若v未访问
            tarjan(v);
            // 返回u时,更新low,判断点
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                son++; // 子树个数
                if (u != root || son > 1) { // u为割点
                    _________ // 根据实际情况编写
                }
            }
        } else // 若v已访问
            low[u] = min(low[u], dfn[v]);
    }
}