割点

对于一张无向图 $G=(V,E)$ ，使得 H 是 G 的连通子图，且不存在 $F$ 满足 $H \subsetneq F \in G$ 且 $F$ 为连通图，则称 $H$ 是 $G$ 的一个连通块/连通分量（connected component），又叫极大连通子图。

由此，我们可以对割点做出如下定义：

对于一个无向图，如果把一个点删除后这个图的极大连通分量数增加了，那么这个点就是这个图的割点（又称割顶）。

Tarjan

处理过程

与有向图的强连通分量相似，我们定义如下两个重要数组：

dfn[]：表示深度优先遍历图时节点 $u$ 被遍历到的次序，即时间戳。
low[]：节点 $u$ 在不通过父亲走过的路的情况下可以到达节点的最小时间戳。

根据割点的定义可知，如果一个节点 $ver$ 是割点，那么必然有一个处于其 DFS 序子树内的节点 $to$ 使得：

$low_{to} \ge dfn_{ver}$

这个意思指的是无论如何走， $to$ 都无法到达 $ver$ 以上的节点，不能回到祖先，那么 $ver$ 即为割点。

然而当 $ver$ 作为搜索的起始点时，由于 $ver$ 以上没有父亲节点，自然无法判断其是否是割点，这种方法并不适用，对于这种情况，我们可以直接特判：记录从 $ver$ 节点开始可以到达的子节点数量，如果大于 $1$ ，则 $ver$ 肯定是割点；而如果只有一个儿子的话，删掉 $ver$ 不会发生任何影响。

考虑如何在搜索的过程不断更新 low[] 数组：

当遍历到当前点 $ver$ 时，令 $low_{ver} \gets dfn_{ver}$ 。
遍历子节点 $to$ 时，如果 $to$ 已经被更新过（ $dfn_{to}$ 有值），那么边 $ver \to to$ 为非树边，要么为前向边（我们不用处理），要么为返祖边（令 $low_{ver} \gets dfn_{to}$ ）。
否则，由于 $to$ 没有被遍历过，在 $ver$ 的搜索子树当中，我们继续搜索 to 的子树，并将传递的值返回，令 $low_{ver} \gets \min(low_{ver}, low_{to})$ 。

伪代码如下（摘自 OI Wiki）：

$\begin{array}{ll} 1 & \textbf{if } v \text{ is a son of } u \\ 2 & \qquad \text{low}_u = \min(\text{low}_u, \text{low}_v) \\ 3 & \textbf{else} \\ 4 & \qquad \text{low}_u = \min(\text{low}_u, \text{dfn}_v) \\ \end{array}$

注意

由于 low[] 数组在 DFS 序子树中具有传递性，直接在子树中传递 low[ver] = min(low[ver], low[to]) 是没有任何问题的。

而如果边 $ver \to to$ 是一条返祖边时，采取 low[ver] = min(low[ver], low[to]) 的更新方式会使得之后的点可以回溯到 $ver$ 的其他点更新时重复上跳，违反了 low[] 数组的初始定义，导致出错。况且 low[] 数组的核心用处是判断 $low_{to} \ge dfn_{ver}$ ，并非求最值，它仅需要找到一个比 $ver$ 更小的点即可，因此 low[ver] = min(low[ver], dfn[to]) 的正确性成立。

详见：关于有向图 Tarjan 算法模板的一些疑问

代码

P3388 【模板】割点（割顶）

给出一个 $n$ 个点， $m$ 条边的无向图，求图的割点。

void tarjan(int ver, int pre)
{
    dfn[ver] = low[ver] = ++ timestamp;	// 初始化时间戳
    int child = 0;	// 记录该节点为根有几个儿子
    for (int i = h[ver]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            child ++;
            tarjan(j, ver);
            low[ver] = min(low[ver], low[j]);
            if (ver != pre && low[j] >= dfn[ver] && !flag[ver])
                res ++, flag[ver] = true;	// 找到一个割点
        }
        else if (j != pre)
            low[ver] = min(low[ver], dfn[j]);
    }
    if (ver == pre && child >= 2 && !flag[ver])
        res ++, flag[ver] = true;	// 特判根节点
}

割边（桥）

与割点的定义类似，如下：

对于一个无向图，如果删掉一条边后图中的连通分量数增加了，则称这条边为桥或者割边。

Tarjan

处理过程

与 Tarjan 算法求解割点的方法类似，我们同样定义两个数组 dfn[] 和 low[] 处理，对于一条割边，以它连接的子树必然无法通过别的边到达它上面的点，即对于一条在 DFS 树上的 $ver \to to$ 边 $edge$ ：

$low_{to} \gt dfn_{ver} \iff egde \in \text{Bridge}$

需要注意的是，在标记一条边时，同时要标记它的反边。

代码

void tarjan(int ver, int from)
{
    dfn[ver] = low[ver] = ++ timestamp;
    for (int i = h[ver]; ~i; i = ne[i])
    {
        int to = e[i];
        if (to == (from ^ 1)) continue;
           if (!dfn[to])
        {
            tarjan(to, i);
            low[ver] = min(low[ver], low[to]);
            if (low[to] > dfn[ver])
                bridge[i] = bridge[i ^ 1] = true, ++ ans;
        }
        else low[ver] = min(low[ver], dfn[to]);
        
    }
}