Tarjan算法详解
本文介绍利用Tarjan算法求无向图割边、割点、点双连通分量和边双连通分量。
一些概念
介绍图论相关概念，注意有些概念适用于有向图，但是本文均特指无向图。
- 连通 图上两个点至少有一条路径连接，则称两个点连通
- 连通图 图上任意两个点都是连通的，则称该图为连通图
- 连通分量
连通图的连通分量就是自身。非连通图可以拆分为几个连通子图，并且这几个连通子图无法再新增点，每一个这样的连通子图都是原图的一个连通分量。
如图 是一个包含5个节点的无向图，其中节点1-2-3和节点4-5各组成一个连通分量。
这很明显的好吧，明显这两部分没连起来嘛
- 割点
如果删除了某个点及所有与其相连的边会导致连通分量个数增加，则该点是割点。(意味着原图中这两个连通分量只能通过这个点连接)
如图节点3是割点，删除3和与3相连的4条边，会发现原图变成了1-2和4-5两个连通分量。
- 割边/桥
如果删除了某个边会导致连通分量个数增加，则该边为割边，又称桥。
如图节点3和4之间的边是割边，删除后原图会变成1-2-3和4-5-6两个连通分量。
这也很明显好吧
- 边双连通
对于图上两点\(u\)和\(v\)，任意删除一条边(且只删除一条)后，\(u\)和\(v\)之间依然是连通的，则称\(u\)和\(v\)为边双连通。对应有边双连通图，边双连通分量。
如下图，4个节点构成一个简单环，删除任意一个边，都可以从另一半绕路连通。
由边双定义可知，边双内部不能有割边(桥)，否则删除桥必然导致“断开”。
注意边双连通具有传递性，比如\(x\)与\(y\)边双连通，\(y\)与\(z\)边双连通，则有\(x\)和\(z\)双连通。
- 点双连通
对于图上两点\(u\)和\(v\)，任意删除一个其它节点及与其相邻边(只删除一个)后，\(u\)和\(v\)之间依然是连通的，则称\(u\)和\(v\)为点双连通。对应有点双连通图，点双连通分量。
点双内部也不能有割点。
注意点双连通不具有传递性，比如\(x\)与\(y\)点双连通，\(y\)与\(z\)点双连通，\(x\)和\(z\)可能不点双连通。如下图：
下面详细介绍原理
\(dfn\)和\(low\)数组
这两个数组是Tarjan算法的精髓之处。
以下所有算法都基于这个\(dfn\)数组和\(low\)数组，记录的都是节点的某个数据信息。下面详细介绍这两个数组的生成。
首先\(dfs\)(深度优先搜索)应该都是比较清楚的，此处先以一棵树为例
对于\(dfn\)数组，\(dfn[i]\)表示的是节点\(i\) 访问时的时间戳，从1开始，每访问一个节点，时间戳+1。
注意 对于每个节点，子节点有多个时，其顺序可能是不确定的，比如对于节点1，可能先访问2，也可能先访问4。
本例下最终的\(dfn=[1,6,3,2,5,4]\)
如果是图而非树，则可能会遇到环，在图上也是可以进行\(dfs\)的，当遇到一个节点已经访问过时，不能再在继续\(dfs\)这个节点，否则会产生死循环。最终可以完整遍历这个图。
\(low\)数组 明确的意义是表示不经过之前\(dfs\)路径而能访问到的最小\(dfn\)值。比较抽象，我们举个具体例子。
实线依然是\(dfs\)的过程，每次访问某个节点时，同时赋值\(dfn[i]=low[i]=time\)。
注意节点5到节点3的红线表示遇到了一个之前出现过的节点，注意这里构成了一个环。
此时，由于\(dfn[3]=3<low[5]=5\)，需要更新节点5的\(low[5]=dfn[3]\)。
特别注意，\(dfs\)向下递归后，还有原路返回的过程，如图虚线的路径。对于每次原路返回时，我们都需要做这个\(low[i]\)的更新过程：
对于每个节点\(u\)的子节点\(v\)，都有\(low[u]=min(low[u],low[v])\)。
上图就是整个\(dfs\)完成后的结果，注意\(low[5]\)和\(low[4]\)的变化。
这里给出Tarjan核心代码，需要仔细理解\(dfs\)的过程和\(dfn,low\)数组的赋值。
//核心代码 C++
int time = 0; //访问子节点的时间戳，每访问一次 ++time
vector<int> low(n);
vector<int> dfn(n);
vector<vector<int>> g(n); //邻接表建图
//u是当前遍历的节点，p是u的父节点，对于根节点0，一般有p=-1
void tarjan(int u, int p)
{
low[u] = dfn[u] = ++time;
//遍历u的每个子节点v
for(auto v : g[u])
{
if(v == p) continue; //经典处理 如果是前往父节点 则跳过。
if(!dfn[v])
{
//如果v尚未访问 则递归调用tarjan
tarjan(v, u);
//对于每个处理完的子节点v 更新u的low值
low[u] = min(low[u], low[v]);
}
//如果v已经访问过 表示遇到环 更新low[u]
else low[u] = min(low[u], dfn[v]);
}
}
//入口 看个人习惯，这里根节点从0开始
//另外注意 如果原始图本身不是连通图，需要枚举所有节点调用tarjan(i,-1)，后续有例子。
tarjan(0, -1);
下面我们利用这两个数组解决具体的不同算法问题。每个问题都是对上述核心算法的稍加修改。
割点
以上图为例，割点显然是节点1和节点3。
- 对于节点3，这一类我们称为非根节点。
对于非根节点\(u\)，是否是割点的条件是存在至少一个子节点\(v\)，满足条件\(low[v]>=dfn[u]\)。
对于节点3，其子节点4和5都是满足这个条件的，所以3是割点。
而对于子节点4，其子节点5\(low[5]=3\)而\(dfn[4]=4\)，不满足条件。
这个\(low[v]>=dfn[u]\) 到底是个什么意思呢？ \(low[v]\) 实际上代表的是，节点v向上返回的最远位置。
如果\(low[v]=dfn[u]\)，说明节点v通过另一条路径能回到节点u。正如本图，节点4可以通过4-5-3回到节点3，而非直接通过4-3回到节点3。
如果\(low[v]>dfn[u]\)，说明子节点要么实际上没有碰到环路，要么碰到环路后返回的节点比节点u要更深。
- 而对于节点1，特别注意，这个节点是我们遍历开始的根节点。
他不能应用上述的判定，假设我们先去掉节点2，会发现节点1只有一个单链连接到节点3，此时\(low[3]>dfn[1]\)，但是节点1此时显然不是割点。
对于根节点，我们需要判定是否有多个子图，这部分跟\(dfn,low\)都没有关系。比如本例中，根节点1有2和3两个子节点对应的子图。所以1是割点。
注意：子图的个数，并不是子节点的个数，因为子节点之间可能会连成环。
下面我们通过模板题来看下具体代码。
我们基于模板题给出C++代码 ACM模式的完整代码。
另外注意，根据题目环境，我们初始节点从1开始，枚举根节点时父节点指定为0。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector<vector<int>> g(n + 1);
for (int i = 0; i < m; i++)
{
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
//tarjan
int time = 0;
vector<bool> flag(n + 1, 0);
vector<int> dfn(n + 1, 0);
vector<int> low(n + 1, 0);
auto tarjan = [&](auto self, int u, int p)->void
{
low[u] = dfn[u] = ++time;
int count = 0; //记录有效的子图个数
for (auto v : g[u])
{
if (p == v) continue;
if (!dfn[v])
{
self(self, v, u);
low[u] = min(low[u], low[v]);
count++; //只有访问未标记的子节点时，子图个数才会+1
if (p == 0 && count >= 2) flag[u] = true; //根节点的判定
if (p > 0 && low[v] >= dfn[u]) flag[u] = true; //非根节点的判定
}
else low[u] = min(low[u], dfn[v]);
}
};
//图不连通的情况下 必须枚举每个节点
for (int i = 1; i <= n; i++)
{
//如果节点i尚未访问，则以tarjan方式访问该节点
if (!dfn[i]) tarjan(tarjan, i, 0);
}
int count = 0;
for (int i = 1; i <= n; i++) if (flag[i]) count++;
cout << count << endl;
for (int i = 1; i <= n; i++) if (flag[i]) cout << i << " ";
}
割边
割边就简单一些了。
枚举当前节点u时，如果某个子节点执行完Tarjan后，如果依然有\(low[v] > dfn[u]\) 则\(u-v\)是割边。
这样理解一下，如果子节点v最终没有通过回路回到u或者u以上的节点，那么u-v这条边就成为u v之间唯一的路径。
割边模板题，这里也直接贴下通过代码，注意这里是LeetCode的核心代码模式。
根据题意，这里初始节点从0开始，相应的父节点指定为-1。
class Solution {
public:
vector<int> dfn, low;
vector<vector<int>> g;
vector<vector<int>> ans;
int time;
void tarjan(int u, int fa)
{
dfn[u] = low[u] = ++time;
for (auto v : g[u])
{
if (v == fa) continue;
if (dfn[v] == 0)
{
tarjan(v, u);
low[u] = min(low[u], low[v]);
//割边判定只有这一处代码
if (low[v] > dfn[u]) ans.push_back(vector<int>{u, v});
}
else low[u] = min(low[u], dfn[v]);
}
}
vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
dfn.resize(n, 0);
low.resize(n, 0);
g.resize(n);
//邻接表建图
for (auto e : connections)
{
g[e[0]].push_back(e[1]);
g[e[1]].push_back(e[0]);
}
//由于原图是连通图 所以只需要枚举任意一个根节点，这里选择节点0。
tarjan(0, -1);
return ans;
}
};
点双连通
双连通分量需要我们将图分解为多个子图，最终求解多组节点，我们需要使用栈存储遍历过的节点，使用一个二维数组存储所有的双连通分量。
一个图的割点可能在多个点双连通子图中。
最后所有的割点与点双连通分量形成一颗树/或森林。可用于点双缩点
下面给出核心代码
int time = 0;
vector<int> low(n), dfn(n);
stack<int> st;
vector<vector<int>> vbcc; // 所有点双连通分量
void Tarjan(int u, int p) {
low[u] = dfn[u] = ++time;
st.push(u);
int count = 0;
for (auto v : g[u])
{
if (v == p) continue;
if (dfn[v] == 0)
{
tarjan(v, u);
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u]) //u以下以v开始到整个栈顶构成一个连通分量
{
vector<int> list;
while (st.top() != v)
{
list.push_back(st.top());
st.pop();
}
//v加入列表
list.push_back(st.top());
st.pop();
//u加入列表 但是u不退栈，因为u可能在多个点双分量里。
list.push_back(u);
vbcc.push_back(list);
}
}
else low[u] = min(low[u], dfn[v]);
}
};
Tarjan(0, -1);
举个复杂一点例子，如图：
经过点双处理后，会形成四个点双连通分量，注意割点3和4的分布。
LCP 54. 夺回据点 点双连通分量，近似模板题。
LeetCode核心代码模式的完整代码
class Solution
{
public:
long long minimumCost(vector<int>& cost, vector<vector<int>>& roads)
{
int n = cost.size();
vector<vector<int>> g(n);
//邻接表建图
for (auto & e : roads)
{
g[e[0]].push_back(e[1]);
g[e[1]].push_back(e[0]);
}
vector<bool> flag(n, false); // 是否是割点
int time = 0;
vector<int> low(n), dfn(n);
stack<int> st;
vector<vector<int>> vbcc; // 所有点双连通分量
//需要同时处理双连通分量和割点
function < void(int, int) > tarjan = [&](int u, int p) {
low[u] = dfn[u] = ++time;
st.push(u);
int count = 0;
for (auto v : g[u])
{
if (v == p) continue;
if (dfn[v] == 0)
{
count++;
tarjan(v, u);
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u])
{
if (u > 0) flag[u] = true; //割点
vector<int> list;
while (st.top() != v)
{
list.push_back(st.top());
st.pop();
}
list.push_back(st.top());
st.pop();
list.push_back(u);
//一个完整的双连通分量
vbcc.push_back(list);
}
}
else low[u] = min(low[u], dfn[v]);
}
if (count >= 2 && u == 0) flag[u] = true; //根节点割点
};
tarjan(0, -1);
//以下做一个事情，缩点后，求树上所有叶节点(设长度为m)的前(m-1)小点权和。
int MX = INT_MAX / 2;
vector<int> mList;
for (auto & list : vbcc)
{
int minVal = MX;
int cc = 0;
for (auto v : list)
{
if (!flag[v]) minVal = min(minVal, cost[v]);
else cc++;
}
if (cc <= 1 && cc < list.size()) mList.push_back(minVal);
}
//如果m=1 特殊处理直接返回这一个节点权值
if (mList.size() == 1) return mList[0];
//以下排序后 返回前(m-1)项和
sort(mList.begin(), mList.end());
long long ans = 0;
for (int i = 0; i < mList.size() - 1; i++) ans += mList[i];
return ans;
}
};
边双连通
与点双不同的地方参见注释，这里给出核心代码。
注意 边双连通里的割点只会在一个连通分量里
所有的桥边与边双形成新的一棵树/或森林。可用于边双缩点
int time = 0;
vector<int> low(n), dfn(n);
stack<int> st;
vector<vector<int>> ebcc; // 所有边双连通分量
void Tarjan(int u, int p) {
low[u] = dfn[u] = ++time;
st.push(u);
int count = 0;
for (auto v : g[u])
{
if (v == p) continue;
if (dfn[v] == 0)
{
tarjan(v, u);
low[u] = min(low[u], low[v]);
}
else low[u] = min(low[u], dfn[v]);
}
//所有子节点处理完毕后 处理边连通问题
if (low[u] == dfn[u])
{
vector<int> list;
while (st.top() != u)
{
list.push_back(st.top());
st.pop();
}
//u加入列表
list.push_back(u);
st.pop();
ebcc.push_back(list);
}
};
Tarjan(0, -1);
同样以上图为例，边双处理后，会形成三个边双连通分量，注意会基于割边(桥) 断开。
P8436 【模板】边双连通分量
边双模板。这个题麻烦之处在于可能出现重边。意味着节点\(u-v\)之间可能有两条边，这样\(u-v\)构成了边双连通。
所以遍历\(u\)的每个节点\(v\)时，不能依据父节点的判定，而是依据反边的判定。
下面这个是不带重边的代码，可以看到Tarjan函数传入的依然是p节点表示父节点。
如果想正确处理重边，需要传入进入时的边的编号，以及需要记录与其对应的反边编号。此处略。
所以说前向星建图好用
//不带重边的无向图的边双连通分量 只能过上面模板题的50分 仅作为边双无重边模板
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector<vector<int>> g(n + 1);
for (int i = 0; i < m; i++)
{
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
//tarjan
int time = 0;
vector<int> low(n + 1), dfn(n + 1);
stack<int> st;
vector<vector<int>> ebcc; // 所有边双连通分量
auto tarjan = [&](auto self, int u, int p)->void
{
low[u] = dfn[u] = ++time;
st.push(u);
int count = 0;
for (auto v : g[u])
{
if (v == p) continue;
if (dfn[v] == 0)
{
self(self, v, u);
low[u] = min(low[u], low[v]);
}
else low[u] = min(low[u], dfn[v]);
}
//所有子节点处理完毕后 处理边连通问题
if (low[u] == dfn[u])
{
vector<int> list;
while (st.top() != u)
{
list.push_back(st.top());
st.pop();
}
//u加入列表
list.push_back(u);
st.pop();
ebcc.push_back(list);
}
};
for(int i = 1; i <= n; i++) if(!dfn[i]) tarjan(tarjan, i, 0);
cout << ebcc.size() << endl;
for (auto list : ebcc)
{
cout << list.size() << " ";
for (auto v : list)
{
cout << v << " ";
}
cout << endl;
}
}