浅谈 Tarjan 算法

chrispang · 2025-07-20 17:10:14 · 算法·理论

修改：

• 2025.07.28，感谢用户 @A_little_badger 指出了错别字。
• 2025.10.31，感谢用户 @Bennyxu2024 指出割点代码的错误。另外以后如果有错误都在博客里面更新，洛谷上不做调整

更好的阅读体验。

最近学了些新算法，过来做下笔记，以免以后忘了。

前置知识

Tarjan 算法的时间复杂度为 O(n + m)。

在除了求最近公共祖先的 Tarjan 算法里，都会用到两个数组和一个概念，在这里写清楚一点，以免后面讲得云里雾里。

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

• 时间戳 \textup{dfn}_x​：表示节点 x​ 第一次被访问的顺序。
• 追溯值 \textup{low}_x​：从节点 x​ 出发，最早能访问到的最早时间戳。

当然，这两个数组的含义在不同的 Tarjan 算法中都会有所变化，到时我会讲清楚的。

最近公共祖先（LCA）

题目：最近公共祖先。

在最近公共祖先里，Tarjan 算法是一个离线算法。

离线算法是指在开始处理数据前，所有输入数据已知且不可更改的算法，例如离散化就是一个经典的代表。‌

众所周知，朴素 LCA 的单次查询在最坏情况下的时间复杂度为 O(n)（n 为总节点数），因此就有了改进算法，将单次查询的时间提高至 O(\log n)。

但是，能否使我们每一次对树的遍历更有价值一些呢，可不可以一次遍历获得不止一个答案甚至是所有答案呢？Tarjan 算法表示这是可以做到的。

知周所众，在以 u​ 为根的子树下，任意两个不属于同一颗以 u​ 的儿子为根的子树的节点（听起来有点晕），它们的 LCA 就是 u​。简单来说，设 \textup{son}_{u,i}​ 表示节点 u​ 的第 i​ 个儿子，x​ 属于 \textup{son}_{u,i}​ 的子树，y​ 属于 \textup{son}_{u,j}​ 的子树。只要 i\ne j​，那么 x​ 与 y​ 的 LCA 就是 u​。

利用这一性质，我们可以想到一个做法：使用 DFS 遍历每一个节点 x，将 x 的子树存入以 x 的父亲为首的集合里面。接着枚举与 x 有关的问题（即在 DFS 开始前离线出来的问题）若问题为“求出 x,y 的 LCA”，且 y 已经被访问过了，那么这个问题的答案即为 y 的首领。

维护首领需要用到并查集，但是这个并查集其实是有点问题，他只能让节点 x 的集合变成 x 父亲节点的集合，即 fa[x] = father，而其它的操作都正常。这样做的目的是为了维护每个节点的当前最大祖先，以达到回答问题的效果。

不过为什么在问题为“求出 x,y​ 的 LCA”中，答案是 find(v) 而不是 find(x) 呢？因为我们已经要求了 y​ 是已经被访问过的节点了，也就是说，y​ 所在的集合首领已经让 y​ 成为这个集合中的一个了，而 x​ 由于还在访问，所以是无法看到自己的最大祖先的。因此我们这里就选择使用 find(y) 来当答案啦！

::::success[代码]

#include <bits/stdc++.h>
using namespace std;

const int N = 500010, M = 2 * N;
int n, m, s, a, b;
vector<int> linker[N];
struct node { int v, w; };
vector<node> query[N];
int fa[N], vis[N], ans[M];
int find(int x) {
    if (x == fa[x]) return x;
    return fa[x] = find(fa[x]);
}

void tarjan(int x) {
    vis[x] = 1; // 做访问标记 
    for (auto to : linker[x])
        if (!vis[to]) { // 不能是自己的父亲 
            tarjan(to); // 接着向下访问 
            fa[to] = x; // 并查集将节点指向节点父亲
            // 注意上述两行代码不能反过来，不然它们的 fa[to] 就都是 root 了 
        }
    for (auto i : query[x]) {
        int v = i.v, w = i.w;
        // 一定要访问过，不然无意义 
        if (vis[v]) ans[w] = find(v);
        // find(v) 才是真答案，因为 find(v) 已经将 v 的集合首领变为 find(v) 了，而 x 还没有
        // 可以这么想一想，如果 v 和 x 不属于同一颗 LCA 的儿子的子树，那么既然 v 已经访问完毕，答案肯定是 v 的集合首领 
    }
}

int main() {
    cin >> n >> m >> s;
    for (int i = 1; i < n; i++) {
        scanf("%d%d", &a, &b);
        linker[a].push_back(b);
        linker[b].push_back(a);
    }
    // 离线 
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &a, &b);
        query[a].push_back({b, i});
        query[b].push_back({a, i});
    }
    for (int i = 1; i <= N; i++) fa[i] = i; // 并查集初始化 
    tarjan(s);
    for (int i = 1; i <= m; i++)
        printf("%d\n", ans[i]);
    return 0;
} 

::::

强连通分量（SCC）

题目：The Cow Prom S。

强连通分量：如果一张有向图，它的任意两个节点都可以互相到达，我们称之为强连通图。如果是一张图的极大的强连通子图，我们称之为强连通分量。

如图，1,2,3,4 组成了一个强连通分量，但 1,2,3,4,5 组成的就不是：

好了现在要用到前面说到的 \textup{dfn} 数组和 \textup{low} 数组了，忘记的回去看。

使用 DFS 遍历每一个节点，当枚举到 x 时，初始化 \textup{dfn}_x 与 \textup{low}_x，并且将其压入栈内（这个栈是用来存储强连通分量的节点的）：

::::success[代码]

dfn[x] = low[x] = ++tim; // 这个 tim 是全局变量
stk[++top] = x, vis[x] = 1; // 将 x 放入栈中，并打上标记

::::

接着枚举 x 的邻点 v，分三种情况：

• 若 v 尚未访问，那么对 v 深搜，并用 \textup{low}_v 更新 \textup{low}_x。因为 x 是 v 的父节点，v 能到达的地方 x 也能到达。
• 若 v 已访问且在栈中，说明 v 是左子树节点或者祖先节点。使用 \textup{dfn}_v 更新 \textup{low}_x。此处使用 \textup{low}_v 更新 \textup{low}_x 可能会被其它强连通分量给污染。
• 若 v 已访问且不在栈中，说明 v 已经被其所在的强连通分量处理了，不需要管它。

::::success[代码]

for (int v : linker[x]) {
    if (!dfn[v]) {
        tarjan(v);
        low[x] = min(low[x], low[v]);
    } else if (vis[v])
        low[x] = min(low[x], dfn[v]);
}

::::

之后处理强连通分量。

若当前枚举到的 x 满足 \textup{dfn}_x=\textup{low}_x，也就表示 x 能到达的最小时间戳的节点就是自己，也就代表着 x 是一个强连通分量上的一个点，那么在栈中在它后面放入的点且现在还在栈中的点与它就可以组成一个强连通分量。所以接下来只要把栈中比 x 后加入栈的节点取出来就可以了。

::::success[代码]

if (dfn[x] == low[x]) {
    ++cnt;
    while (1) {
        int y = stk[top--]; // 取出节点
        vis[y] = 0; // 取消进栈标记
        scc[y] = cnt; // 记录强连通分量中的节点属于哪一个分量
        ++siz[cnt]; // 记录强连通分量大小
        if (x == y) break; // 枚举到 x 出栈就可以了
    }
}

::::

为了完成这道题，这里继续给出主函数代码，比较简单，如果前面的看懂了，主函数肯定不成问题：

::::success[代码]

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> a >> b, add(a, b);
    for (int i = 1; i <= n; i++) // 整个图可能不连通，要一一枚举
        if (!dfn[i]) tarjan(i);
    for (int i = 1; i <= cnt; i++)
        if (siz[i] > 1) ans++;
    cout << ans << endl;
    return 0;
}

::::

割点

题目：割点。

割点：在一张无向图中，如果去掉一个点可以使图的连通块增加，则这个点被称之为割点。

如图，4​ 就是一个割点：

好吧这个算法也是要用到 \textup{dfn} 和 \textup{low} 的，而且我可以提前告诉你：割点算法与强连通分量的代码长得很像，需要好好区分。

还是使用 DFS 枚举 x​，分两种情况：

• 若 x​ 不为根节点，当搜索树上存在一个 x​ 的儿子 y​，满足 \textup{low}_y \ge \textup{dfn}_x​，则 x​ 为割点。
• 若 x​ 为根节点，当搜索上存在两个 x​ 的儿子满足上述条件时，x​ 为割点。

那么 \textup{low}_y \ge \textup{dfn}_x 是什么意思呢？这个不等式其实代表着 y 最远能到达的最小的时间戳也不会超过 x 的时间戳，也就表示着 x 的父亲节点 y 是碰不着的，那么此时如果断开，必定会增加至少一个连通块。

那么为什么根节点需要拥有两个这样的儿子呢，举个例子你就知道了。

如图，1 作为根节点有着 2 这样满足条件的儿子，但是将其去掉后图的连通块仍然是 1：

好了，在知道以上判断条件后，代码也不难写出了.

但是，还是要注意一点：数据是有重边的，而重边就可以往回走了。但是我们这个判断就直接把这个机会给“杀死”了。

因此，我们不能根据顶点来判断，而是要根据边来判断，条件是不能走上一次走过的边。我们为了判边，就需要给 vector 多绑上一个 int 保存边的编号以判断。

::::success[代码]

// Tarjan算法 O(n + m)
#include<bits/stdc++.h>
using namespace std;

const int N = 20010;
int n, m, a, b, ans;
vector<int> linker[N], ne[N];
int dfn[N], low[N], tim, top;
int iscut[N];
void add(int a, int b) {
    linker[a].push_back(b);
}

void tarjan(int x, int isroot) {
    dfn[x] = low[x] = ++tim;
    int child = 0;
    for (int v : linker[x]) {
        if (!dfn[v]) {
            tarjan(v, 0);
            low[x] = min(low[x], low[v]);
            if (low[v] >= dfn[x]) child++;
        } else low[x] = min(low[x], dfn[v]);
    }
    if (!isroot && child >= 1 || isroot && child >= 2) iscut[x] = 1;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1, a, b; i <= m; i++) {
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    for (int i = 1; i <= n; i++) // 可能不连通
        if (!dfn[i]) tarjan(i, 1);
    for (int i = 1; i <= n; i++)
        ans += iscut[i];
    cout << ans << endl;
    for (int i = 1; i <= n; i++)
        if (iscut[i]) cout << i << " ";
    return 0;
}

::::

割边

题目：炸铁路。

注：本题使用暴力解法也可以通过 ，因此你可以不用学这个算法。

割边：给定一张无向图，若存在一条边，将这条边去掉后整个图的连通块数量增加，则这条边为割边。

如图，边 [4,5] 就是一条割边：

好吧我就告诉你吧，其实 Tarjan 算法长得都挺像的（除了那个 LCA 以外）

还是使用 DFS 算法，设当前枚举到 x​，若 x​ 存在一个子节点 y​，满足 \textup{low}_y > \textup{dfn}_x​，则 [x,y]​ 这条边就是割边。