一、Tarjan 在解决什么问题

1.1 问题背景

从图的连通性切入：

在一个无向连通图中：

  • 删除某个顶点后，图可能不再连通；

  • 删除某条边后，图也可能不再连通。

这些关键顶点和关键边分别称为：

  • 割点

  • 割边，也叫桥

1.2 基本定义

割点

在无向连通图中，删除某个顶点以及与它相连的所有边后，图的连通分量数量增加，那么这个顶点称为割点。

割边

在无向连通图中，删除某条边后，图的连通分量数量增加，那么这条边称为割边或桥。

1.3 为什么不能暴力枚举

暴力方法：

  • 依次删除每个顶点，再执行一次 DFS；

  • 依次删除每条边，再执行一次 DFS。

假设顶点数为 nn ，边数为 mm ，复杂度可能达到： O(n(m+n))O(n(m+n))

而 Tarjan 算法只需要一次 DFS： O(n+m)O(n+m)

二、从原图到 DFS 搜索树

2.1 DFS 搜索树

对无向图进行 DFS 时，第一次访问一个节点的边会形成一棵 DFS 搜索树。

注意：

DFS 树只表示搜索过程，并不是把原图真的变成了一棵树。

没有进入 DFS 树的边仍然存在，并且恰恰是这些边，使某些子树能够绕回祖先。

2.2 两类重要的边

在无向图的 DFS 过程中，可以重点关注两类边。

树边

第一次访问新节点时经过的边。例如：u -> v

当 v 尚未访问时，边 (u,v) 是 DFS 树中的树边。

返祖边

当前节点或其子孙节点，可以通过某条非树边连接到当前节点的祖先。

这条边会显著影响割点和桥的判断。

三、理解 dfn 和 low

3.1 dfn[u] 的含义

dfn[u] 表示节点 u 在 DFS 中第一次被访问的时间戳。

dfn 越小，说明节点越早被访问，通常在 DFS 树中的位置也越靠上。

3.2 low[u] 的含义

low[u] 表示：

从节点 u 出发，只经过其 DFS 子树中的若干条树边，并且至多经过一条返祖边，能够到达的最早祖先的 dfn。

3.3 low 的三种更新来源

初始化：

dfn[u] = low[u] = ++timestamp;

情况一：发现未访问节点

if (!dfn[v]) {
    tarjan(v, edge);
    low[u] = min(low[u], low[v]);
}

含义：节点 v 的子树能到达的最早祖先，也可能是节点 u 的子树能够到达的最早祖先。

情况二：发现已访问节点

else {
    low[u] = min(low[u], dfn[v]);
}

含义：

节点 u 找到了一条直接连接到已访问节点 v 的边。

如果 v 是祖先节点，那么这条边就是返祖边，可以用 dfn[v] 更新 low[u]。

情况三：不能用父边更新

在无向图中，每条边会被存储两次。

节点 u 通过父边来到节点 v 后，节点 v 不能再把同一条边当成返祖边绕回 u。

因此需要排除进入当前节点的反向边。

四、一个统一的核心问题

在分别学习割点和桥之前，先提出一个统一问题：

节点 v 的 DFS 子树，能不能绕过父节点 u 或父边 (u,v)，回到更高的祖先？

假设 (u,v) 是 DFS 树中的一条树边：

关键是比较： low[v]low[v] 和： dfn[u]dfn[u]

情况一：low[v] < dfn[u]

说明 v 的子树可以通过返祖边到达 u 的某个真祖先。

因此：

  • 删除边 (u,v)，v 的子树仍能绕回去；

  • 删除节点 u，v 的子树也可能通过返祖边连接到更上层。

情况二：low[v] = dfn[u]

说明 v 的子树能够回到 u，但是无法绕过 u 回到 u 的祖先。

此时：

  • 删除边 (u,v) 后，子树仍然可以通过其他边回到 u，所以 (u,v) 不是桥；

  • 删除节点 u 后，这些路径也随之消失，所以 u 可能是割点。

这正是割点使用 >=，而桥使用 > 的关键。

情况三：low[v] > dfn[u]

说明 v 的整棵子树连 u 都无法通过其他路径到达。除了父边 (u,v)，子树没有任何其他路径能够回到 u 或更高祖先。

因此：

  • (u,v) 一定是桥；

  • 如果 u 不是 DFS 根节点，那么 u 也是割点。

五、割边判定

对于 DFS 树边 (u,v)，其中 u 是 v 的父节点：low[v]>dfn[u]low[v]>dfn[u] 则 (u,v) 是桥。

六、割点判定

割点需要区分：

  • 非根节点；

  • DFS 根节点。

6.1 非根节点

假设 u 不是 DFS 根节点，并且 v 是 u 的一个 DFS 子节点。

如果：low[v]≥dfn[u]low[v] \ge dfn[u] 则 u 是割点。

6.2 根节点

对于 DFS 根节点，它没有祖先，因此不能使用普通节点的判断逻辑。

根节点是否为割点，只取决于：

DFS 根节点有多少棵独立的 DFS 子树。

如果根节点有至少两个 DFS 子节点，那么删除根节点后，这些子树之间无法互相到达。

因此：如果根节点的 DFS 子节点数量≥2，则根节点就是割点。

七、代码

7.1 伪代码

tarjan(u, parent_edge):
    dfn[u] = low[u] = ++timestamp

    for each edge (u, v):
        if v 没有访问:
            tarjan(v)
            low[u] = min(low[u], low[v])

            if low[v] > dfn[u]:
                (u, v) 是桥

            if u 不是根节点 && low[v] >= dfn[u]:
                u 是割点

        else if 当前边不是父边:
            low[u] = min(low[u], dfn[v])

    如果 u 是根节点且 DFS 子节点数 >= 2:
        u 是割点

7.2 完整模板

struct Edge {
    int to;
    int id;
};

vector<Edge> g[N];

int dfn[N];
int low[N];
int timer;
bool is_bridge[M];
bool iscut[N];

void tarjan(int u, int parent_id) {
    dfn[u] = low[u] = ++ timer;
    int child_count = 0;
    for (auto [v, edge_id] : g[u]) {
        if (edge_id == parent_id) {
            continue;
        }
        if (!dfn[v]) {
            child_count++;
            tarjan(v, edge_id);
            low[u] = min(low[u], low[v]);
            // 判断桥
            if (low[v] > dfn[u]) {
                is_bridge[edge_id] = true;
            }
            // 非根节点的割点判断
            if (parent_id != -1 && low[v] >= dfn[u]) {
                is_cut[u] = true;
            }
        } else {
            // 返祖边
            low[u] = min(low[u], dfn[v]);
        }
    }
    // DFS 根节点特判
    if (parent_id == -1 && child_count >= 2) {
        is_cut[u] = true;
    }
}