C++Tarjan
先放代码。
#include <bits/stdc++.h>
using namespace std;
const int N=1000005, M=5000005;//N:节点数,M:边数
int head[N],ver[M*2],Next[M*2];//邻接表存储图
int cut[N];//cut[i]:节点i是否为割点
int dfn[N],low[N],st[N];//dfn:时间戳,low:最早可到达时间,st:栈
int n,m,tot=1,num,root,top,cnt;//tot:边数,num:时间戳,root:根节点,top:栈顶,cnt:点双连通分量数量
vector<int> dcc[N*2];//存储每个点双连通分量的节点
void add(int x,int y) {ver[++tot]=y,Next[tot]=head[x],head[x]=tot;}//邻接表存储图
// Tarjan算法实现，用于计算点双连通分量
void tarjan(int x)
{
// 初始化当前节点的dfn和low值，num为时间戳
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]; // 邻接节点y
// 如果节点y未被访问过（深度优先搜索）
if(!dfn[y])
{
tarjan(y); // 递归访问节点y
low[x]=min(low[x],low[y]); // 更新当前节点的low值
// 判断x是否为割点：如果low[y] >= dfn[x]
if(low[y]>=dfn[x])
{
flag++; // 子节点数量加1
// 割点判断条件：
// 1. 如果x不是根节点，且满足条件，则x是割点
// 2. 如果x是根节点，需要至少有两个子节点满足条件
if(x!=root||flag>1) cut[x]=1;
// 创建新的点双连通分量
cnt++;
int z;
// 从栈中弹出节点，直到弹出节点y
do
{
z=st[top--]; // 弹出栈顶节点
dcc[cnt].push_back(z); // 将节点加入当前点双连通分量
}while(z!=y);
// 将割点x也加入当前点双连通分量
dcc[cnt].push_back(x);
}
}
// 如果节点y已被访问过，通过反向边更新low值
else low[x]=min(low[x],dfn[y]);
}
}
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);//从未访问的节点开始tarjan
}
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;
}众所周知，第一次看到这一坨代码，对于正常人（Tarjan本人和dalao除外）来说，应该不会有人能看懂吧？
以上是一个使用Tarjan算法求无向图的点双连通分量的程序。
点双连通分量（Biconnected Component）是指在一个无向图中，一个极大的子图，其中任意两个点之间至少存在两条点不重复的路径。
注意：点双连通分量中，如果该分量包含的边数大于1，那么它不会包含割点。但是，实际上，一个割点可能会属于多个点双连通分量。
代码分析：
-
图的存储：使用邻接表，无向边存储为两条有向边。
-
数组说明：
head, ver, Next: 邻接表
cut: 标记节点是否为割点
dfn: 深度优先搜索遍历时的时间戳
low: 该节点能够通过反向边到达的最早的时间戳
st: 栈，用于存储当前已经访问过的节点，以便在找到一个点双连通分量时弹出节点。
dcc: 存储每个点双连通分量的节点，注意这里开了N*2，因为一个割点可能属于多个点双连通分量。 -
变量说明：
n, m: 节点数和边数
tot: 边的计数器，从1开始（因为邻接表中使用成对存储，0和1为一条无向边，2和3为另一条，所以初始化tot=1）
num: 时间戳
root: 当前搜索的根节点
top: 栈顶指针
cnt: 点双连通分量的计数器 -
Tarjan算法：
从根节点开始进行深度优先搜索，对每个节点x，初始化dfn[x]=low[x]=++num，并将节点入栈。
然后遍历x的所有邻接节点y：
如果y没有被访问过，则递归访问y，并更新low[x]=min(low[x], low[y])。
然后判断：如果low[y] >= dfn[x]，则说明x是一个割点（除了根节点需要特殊判断外），并且此时栈中从栈顶到y之间的节点（包括y）和x构成了一个点双连通分量。
注意：这里判断割点的条件是low[y] >= dfn[x]，并且对于根节点，需要至少两个这样的子节点。
如果y已经访问过，则用dfn[y]更新low[x]（注意：这里用dfn[y]而不是low[y]，是因为我们判断的是通过反向边能够到达的节点的dfn值）。 -
注意：孤立点（即没有邻接边的节点）也被视为一个点双连通分量。
-
输出：先输出点双连通分量的数量，然后依次输出每个点双连通分量的节点数以及节点。
一、算法概述
Tarjan算法是由美国计算机科学家罗伯特·塔扬（Robert Tarjan）在1972年提出的一种基于深度优先搜索（DFS）的图论算法。该算法能够在线性时间复杂度O(V+E) 内解决多种图论问题，包括：
-
强连通分量（有向图）
-
双连通分量（无向图）
-
割点和桥（无向图）
-
最近公共祖先（LCA）（非人哉，应该没人想用）
二、基本概念解析
2.1 点双连通分量
定义：在一个无向图G中，如果任意两个不同的顶点u和v之间都存在至少两条点不重复的路径（即路径上除端点外没有公共顶点），则称G是点双连通的。
性质：
-
点双连通分量是极大的点双连通子图
-
不同的点双连通分量至多共享一个顶点（割点）
-
割点属于多个点双连通分量
-
非割点只属于一个点双连通分量
2.2 割点（Articulation Point）
定义：删除该顶点及其关联边后，图连通分量数增加的顶点。
判断条件（对于DFS树中的非根节点u）：
存在子节点v，使得
对于根节点，需要至少两个这样的子节点。
三、核心数据结构
// 邻接表存储图
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
if(!dfn[y]) {
tarjan(y);
low[x] = min(low[x], low[y]);
// ... 后续处理
}递归访问未访问的邻居，更新low值。
步骤3：割点判断
if(low[y] >= dfn[x]) {
flag++;
if(x != root || flag > 1) cut[x] = 1;
}-
low[y] >= dfn[x]：意味着从y出发无法通过回边到达x的祖先
-
删除x后，y及其子树与图的其余部分断开
-
根节点需要至少两个这样的子节点才为割点
步骤4：分量提取
cnt++;
int z;
do {
z = st[top--];
dcc[cnt].push_back(z);
} while(z != y);
dcc[cnt].push_back(x);不断弹出栈顶节点直到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)
-
七、示例演示
示例图：
在鲸鱼(Deep****)的帮助下，我画出了这个：
1---2---3 | / | / | 4---5---6
执行过程：
-
从节点1开始DFS
-
发现割点2、5
-
提取点双连通分量：
-
分量1: {1, 2, 4}
-
分量2: {2, 3, 5}
-
分量3: {2, 4, 5}
-
分量4: {3, 5, 6}
-
八、应用场景
-
网络可靠性分析：识别关键节点（割点）
-
电路设计：避免单点故障
-
交通规划：找出交通枢纽
-
社交网络：发现社区结构
-
编译器优化：识别循环结构
九、常见问题与优化
9.1 自环处理
cpp
if(x == y) continue; // 跳过自环
9.2 重边处理
如果需要处理重边，可以使用邻接矩阵或修改邻接表结构。
9.3 内存优化
-
使用vector代替静态数组
-
动态分配内存
9.4 算法变体
cpp
// 求桥（割边）
if(low[y] > dfn[x]) {
// (x, y) 是桥
}
十、总结
Tarjan算法是图论中极其重要的算法之一，其精妙之处在于：
-
一次DFS完成多项任务
-
栈的巧妙使用提取连通分量
-
low数组的核心作用判断连通性
掌握Tarjan算法不仅有助于解决具体问题，更能加深对图论本质的理解。建议读者在理解基础上，亲手实现并调试几个测试用例，真正掌握这一经典算法。
相关题目：
-
POJ 1523 SPF（割点）
-
UVA 315 Network（割点）
-
UVA 10199 Tourist Guide（点双连通分量）
Agent 垂直技术社区，欢迎活跃、内容共建。
更多推荐
28
0- 0
已为社区贡献2条内容
所有评论(0)