C++ Tarjan 算法详解：点双连通分量与割点

本文介绍使用 Tarjan 算法求无向图的点双连通分量。点双连通分量（Biconnected Component）是指在一个无向图中，一个极大的子图，其中任意两个点之间至少存在两条点不重复的路径。注意：点双连通分量中，如果该分量包含的边数大于 1，那么它不会包含割点。但是，实际上，一个割点可能会属于多个点双连通分量。

一、算法概述

Tarjan 算法是由美国计算机科学家罗伯特·塔扬在 1972 年提出的一种基于深度优先搜索（DFS）的图论算法。该算法能够在线性时间复杂度 O(V+E) 内解决多种图论问题，包括：

1. 强连通分量（有向图）
2. 双连通分量（无向图）
3. 割点和桥（无向图）
4. 最近公共祖先（LCA）

二、基本概念解析

2.1 点双连通分量

定义：在一个无向图 G 中，如果任意两个不同的顶点 u 和 v 之间都存在至少两条点不重复的路径（即路径上除端点外没有公共顶点），则称 G 是点双连通的。 性质：

• 点双连通分量是极大的点双连通子图
• 不同的点双连通分量至多共享一个顶点（割点）
• 割点属于多个点双连通分量
• 非割点只属于一个点双连通分量

2.2 割点（Articulation Point）

定义：删除该顶点及其关联边后，图连通分量数增加的顶点。 判断条件（对于 DFS 树中的非根节点 u）： 存在子节点 v，使得 low[v] >= dfn[u]。 对于根节点，需要至少两个这样的子节点。

三、核心数据结构

// 邻接表存储图
int head[N], ver[M * 2], Next[M * 2]; // 无向边存两次
int tot = 1; // 从 1 开始，方便异或找反向边
// Tarjan 算法核心数组
int dfn[N]; // DFS 序（时间戳）
int low[N]; // 通过回边能到达的最小 dfn
int st[N]; // 栈，存储当前分量中的节点
int top; // 栈顶指针
// 结果存储
vector<int> dcc[N * 2]; // 存储每个点双连通分量
int cut[N]; // 标记割点
int cnt; // 点双连通分量计数器

四、算法流程详解

4.1 深度优先搜索框架

void tarjan(int x) {
    dfn[x] = low[x] = ++num; // 初始化时间戳
    st[++top] = x; // 节点入栈
    // 特殊情况：孤立节点
    if (x == root && head[x] == 0) {
        dcc[++cnt].push_back(x);
        return;
    }
    int flag = 0; // 记录满足条件的子节点数
    for (int i = head[x]; i; i = Next[i]) {
        int y = ver[i];
        if (!dfn[y]) { // 未访问节点
            tarjan(y);
            low[x] = min(low[x], low[y]);
            if (low[y] >= dfn[x]) {
                flag++;
                if (x != root || flag > 1) cut[x] = 1;
                cnt++;
                int z;
                do {
                    z = st[top--];
                    dcc[cnt].push_back(z);
                } while (z != y);
                dcc[cnt].push_back(x); // 割点属于多个分量
            }
        } else {
            low[x] = min(low[x], dfn[y]);
        }
    }
}

4.2 关键步骤分析

步骤 1：初始化与递归

• 为当前节点 x 分配时间戳 dfn[x]
• 初始化 low[x] = dfn[x]，表示当前能到达的最小时间戳
• 节点入栈，为后续弹出分量做准备

步骤 2：处理子节点 y

递归访问未访问的邻居，更新 low 值。

步骤 3：割点判断

if (low[y] >= dfn[x])：意味着从 y 出发无法通过回边到达 x 的祖先。删除 x 后，y 及其子树与图的其余部分断开。根节点需要至少两个这样的子节点才为割点。

步骤 4：分量提取

不断弹出栈顶节点直到 y，再加上割点 x，构成一个点双连通分量。

步骤 5：回边处理

else low[x] = min(low[x], dfn[y])。通过回边更新 low 值，注意这里是 dfn[y] 而不是 low[y]。

五、完整代码解析

5.1 图构建

void add(int x, int y) {
    ver[++tot] = y;
    Next[tot] = head[x];
    head[x] = tot;
}
// 无向图添加边
add(x, y);
add(y, x); // 双向边

5.2 主函数

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        if (x == y) continue; // 处理自环
        add(x, y), add(y, x);
    }
    // 遍历所有连通分量
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) {
            root = i;
            tarjan(i);
        }
    }
    // 输出结果
    cout << cnt << '\n';
    for (int i = 1; i <= cnt; i++) {
        cout << dcc[i].size();
        for (int j = 0; j < dcc[i].size(); j++) {
            cout << ' ' << dcc[i][j];
        }
        cout << '\n';
    }
    return 0;
}

六、算法复杂度分析

• 时间复杂度：O(V + E)。每个节点访问一次（DFS），每条边处理两次（无向图）。
• 空间复杂度：O(V + E)。邻接表存储图，栈空间 O(V)，结果存储 O(V)。

七、示例演示

示例图结构

1---2---3 | / | | / | 4---5---6

执行过程

1. 从节点 1 开始 DFS
2. 发现割点 2、5
3. 提取点双连通分量：
   • 分量 1: {1, 2, 4}
   • 分量 2: {2, 3, 5}
   • 分量 3: {2, 4, 5}
   • 分量 4: {3, 5, 6}

八、应用场景

1. 网络可靠性分析：识别关键节点（割点）
2. 电路设计：避免单点故障
3. 交通规划：找出交通枢纽
4. 社交网络：发现社区结构
5. 编译器优化：识别循环结构

九、常见问题与优化

9.1 自环处理

if (x == y) continue; // 跳过自环

9.2 重边处理

如果需要处理重边，可以使用邻接矩阵或修改邻接表结构。

9.3 内存优化

• 使用 vector 代替静态数组
• 动态分配内存

9.4 算法变体

// 求桥（割边）
if (low[y] > dfn[x]) {
    // (x, y) 是桥
}

十、总结

Tarjan 算法是图论中极其重要的算法之一，其精妙之处在于：

1. 一次 DFS 完成多项任务
2. 栈的巧妙使用提取连通分量
3. low 数组的核心作用判断连通性

掌握 Tarjan 算法不仅有助于解决具体问题，更能加深对图论本质的理解。建议读者在理解基础上，亲手实现并调试几个测试用例。

相关题目：

• POJ 1523 SPF（割点）
• UVA 315 Network（割点）
• UVA 10199 Tourist Guide（点双连通分量）