Tarjan 强连通分量学习笔记
pipilong2024 · · 算法·理论
前言
声明：跳过本部分的阅读并不影响您学习算法。
其实笔者老早一段时间就已经接触到连通一系列问题了，当时是在洛谷网校听的，老师讲的很好，就是我当堂并没有听懂。
大概是在一两周后吧，我去查了很多资料，还发帖求助过，不过越查越乱。我发现基本上每个博客甚至是教辅，都有对 Tarjan 不同的解释。就以对图边的分类来讲吧，OI-wiki 上分成了四种边，洛谷网校上分成了三种边，《算法竞赛》上分成了两种边，《信息学奥赛一本通》上甚至没有分类。类似于上述的例子还有很多。
于是我就决定先放一放。
几天前碍于 csp，决定重新学一学，通过更广的学习面，于是有了本篇博客。旨在想用蒟蒻的更好理解的语言，为大家讲清这个“庞然大物”。与其说是写给自己的学习笔记，不如说是给后人的“避坑指南”。
记录
如果您还能看到这段话，代表笔者还打算继续更新。 目前计划：更新边双点双（会重新写一篇博客）。
- upd 2025.09.24 构思好了介绍强连通分量的框架，同时手搓（手写）了一份“小博客”。
- upd 2025.09.27 更新完了除例题外的所有部分。
- upd 2025.09.29 写完了所有部分。
- upd 2025.10.06 发现了一处笔误。
强连通分量
概念理解
- 强连通：在一个有向图
G 中，如果存在两个节点u,v 是互相可达的，即从节点u 开始，存在一条路径到达节点v ，同时节点v 也存在一条路径到达节点u ，则称u 和v 是强连通的。 - 强连通图：如果一个有向图
G 中，所有节点互相强连通，则称G 是强连通图。 - 强连通分量（Strong Connect Component，下文直接将其称为 SCC）：对于一个有向图
G ，如果 ta 不是强连通图，那么必然可以将其分为多个强连通子图（一个点构成的图也是强连通图），如果每个强连通子图都是极大的，那么我们认为这些“极大的强连通子图”即为强连通分量。
其中极大的意思是无法在扩张了，满足对于一个 SCC，不存在一个不属于该 SCC 的节点与该 SCC 中所有节点互相强连通。
以上图举例，我们认为
算法讲解
让我们先画一个图。
为了引出算法，让我们再画一个 DFS 搜索树。
由于笔者太垃圾了，并不会对边进行上色，就将就着看吧（（（。
假设按照
好，接下来让我们直接推出一个定理。
- 不存在两个节点
u 和v ，满足两点不为祖孙关系，且在u 和v 的子树中有非树边互相连接。换句话说，如果在u 的子树中有一个点由一条非树边指向v 的子树的某个点，那么v 的子树中就一定没有一个点由一条非树边指向u 的子树的某个点。
证明：
因为两个点访问顺序必然有一个先后，当访问其中一个节点的子树时，必然会顺着那条所谓的非树边访问另外一个未被访问的节点的子树的某个节点，那么那条非树边就成了树边了，证毕。
为了方便后面的表述，我们引入一个数组 dfn，为时间戳，表示每个节点被 DFS 搜索到的顺序。
一般用代码这么实现：
void dfs(int u, int fa) {
dfn[u] = ++timestamp;
for (auto v : e[u]) {
if (v == fa) continue;
dfs(v, u);
}
}
for (int i = 1; i <= n; i++) if (!dfn[i]) dfs(i, i);然后再定义一个 SCC 中的根为其中 dfn 最小的节点。
让我们再引出一个定理：
- 一个 SCC 中的所有点必然出现在其的根的子树中。
证明：
使用反证法。
如果一个 SCC 中的点x 不在根的子树中，而是根的祖先，那么x 的dfn必然小于 SCC 的根，矛盾。
如果一个 SCC 中的点x 与根没有关系（指不是祖孙关系），那么想要与根强连通，必然需要来回的两条非树边，这样就违背了前面的定理。
故证毕。
至此，你已经理解了在强连通分量中，Tarjan 算法的主要应用。
那么如何判断在根的子树中那些节点属于 SCC 呢。我们需要引入一个新的数组 low，也就是通过最多一条非树边能到达的 dfn 最小的祖先的 dfn。
只要当存在一个节点
上述的定理可能会很无厘头，甚至荒谬，笔者并没有水平可以证明它（如果您有证明过程，欢迎在评论区给出），但是我可以保证你举不出反例。
或许你会觉得很晕，让我们回到最开始的图来举例吧。
在上述图中，SCC 有三个，分别为 dfn 值分别为 low 值分别为
让我们看看 low 的更新步骤。
- 如果节点
u 可以通过一条边访问一个未被访问的节点v ，那么该边为树边。我们需要先搜索节点v ，然后更新\text{low}_u=\min\{\text{low}_u,\text{low}_v\} ，因为树边并不影响我们对于“经过最多一条非树边”的限制。 - 如果节点
u 可以通过一条边访问自己的祖先v ，那么该边为非树边。我们更新\text{low}_u=\min\{\text{low}_u,\text{dfn}_v\} 。注意必须得用\text{dfn}_v 更新，因为已经消耗了“最多一条非树边”的限制。 - 如果节点
u,v 没有祖孙关系，那么什么也不做。
然后是回溯，我们需要再引入一个栈辅助。每个节点
怎么样，很神奇吧。同样的，无法证明其正确性，但是可以很轻易的证明所有不为同一个 SCC 的点
上述推导建议自己再多举几个例子，稍微理解后再往下看，如果还有疑问，可以直接提出。
为了更加实际些，我将给出模板代码以加深印象（Tarjan 模板形式很多，建议选择一种自己最喜欢的背下来，今后就不要改了）。
#define time lsdfjld//为了避免变量名重复，先打一个乱码
/*
dfn，low：意义如上文描述，为时间戳，通过最多一条非树边能到达的最小的时间戳
st：栈
cnt：每一个 SCC 的编号 sccid：每个点属于哪一个 SCC（存储的是 cnt 的编号）
你可能在别的地方看到的都是 sccno，其实是一个东西，只是我觉得 sccid 好听点（（（
*/
void dfs(int u) {
dfn[u] = low[u] = ++time;//初始化
st.push(u);//压栈
for (auto v : e[u]) {
if (!dfn[v]) {//时间戳为0表示的是还未访问过，也就是该边为树边
dfs(v);
low[u] = min(low[u], low[v]);
} else if (!sccid[v]) low[u] = min(low[u], dfn[v]);
/* sccid为0表示还在栈中，也就是v是u的祖先节点 */
//和上文的更新一样
}
if (dfn[u] != low[u]) return;//不同的话直接返回
++cnt;//相同表示又多了一个 SCC
while (!st.empty()) {
int top = st.top();
st.pop();
sccid[top] = cnt;//存储编号
if (top == u) break;//弹到自己了就结束
}
}例题讲解
P2863 [USACO06JAN] The Cow Prom S
传送门
一个很板很板的题，再弹栈的时候判断一下 SCC 的元素即可。
具体请见代码。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define time sdkljldjf
const int maxn = 1e4 + 10;
int n, m, ans = 0;
int dfn[maxn], low[maxn], time;
int cnt, sccid[maxn];
stack<int>st;
vector<int>e[maxn];
void dfs(int u) {
dfn[u] = low[u] = ++time;
st.push(u);
for (auto v : e[u]) {
if (!dfn[v]) {
dfs(v);
low[u] = min(low[u], low[v]);
} else if (!sccid[v]) low[u] = min(low[u], dfn[v]);
}
if (low[u] != dfn[u]) return;
int sum = 0;//统计 SCC 的个数
cnt++;
while (!st.empty()) {
int top = st.top();
st.pop();
sccid[top] = cnt;
sum++;
if (top == u) break;
}
if (sum > 1) ans++;//统计答案
}//其余一模一样
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1, a, b; i <= m; i++) cin >> a >> b, e[a].push_back(b);
for (int i = 1; i <= n; i++) if (!dfn[i]) dfs(i);
cout << ans;//输出
return 0;
}P3387【模板】缩点
传送门
首先我们要知道一个关于 SCC 的定理。
- 一个点必然可以通过若干条路径遍历完 SCC 内的所有点并回到起点。
这个很好证明，强连通嘛，过去回来。
那么一条贪心策略就呼之欲出了。
每到一个点，就将其 SCC 内的所有点都遍历一次。
不仅白白更新了答案，又回到了起点，稳赚不赔。
然后我们就引出了连通性中一个最常见的分支，也就是缩点。
在本题中，缩点实际上就是通过将每个 SCC 缩成一个点，将原图化简成一个 DAG（有向无环图）。
DAG 能干的事可多了，因为它可以进行拓扑排序，这样我们就可以进行 DP 了。
回到这道题中，我们可以将每个 SCC 缩成一个点，同时将权值累加，最后跑一个类似于 LIS（最长上升子序列）的 DP 即可。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 10;
#define int long long
#define time lsdfjld
int n, m, a[maxn];
int time, dfn[maxn], low[maxn], cnt, sccid[maxn];
int V[maxn], ind[maxn], f[maxn];
stack<int> st;
vector<int> e[maxn], re[maxn], rer[maxn], order;
void dfs(int u) {
dfn[u] = low[u] = ++time;
st.push(u);
for (auto v : e[u]) {
if (!dfn[v]) {
dfs(v);
low[u] = min(low[u], low[v]);
} else if (!sccid[v]) low[u] = min(low[u], dfn[v]);
}
if (dfn[u] != low[u]) return;
++cnt;
while (!st.empty()) {
int top = st.top();
st.pop();
sccid[top] = cnt, V[cnt] += a[top];//累计SCC的总点权
if (top == u) break;
}
}//板子了，没什么好说的
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1, u, v; i <= m; i++) {
cin >> u >> v;
e[u].push_back(v);
}
for (int i = 1; i <= n; i++) if (!dfn[i]) dfs(i);
for (int i = 1; i <= n; i++) {
for (auto j : e[i]) {
int u = sccid[i], v = sccid[j];
if (u == v) continue;
re[u].push_back(v);//正边
rer[v].push_back(u);//反边
ind[v]++;//拓扑用的数组，我也不知道叫什么，作用是统计入度
}
}
queue<int> q;
for (int i = 1; i <= cnt; i++) if (!ind[i]) q.push(i);
while (!q.empty()) {
int u = q.front();
q.pop();
order.push_back(u);//order意为顺序
for (auto v : re[u]) {
ind[v]--;
if (!ind[v]) q.push(v);
}
}
//拓扑板子
int ans = 0;
for (auto i : order) {
f[i] = V[i];//初值为自己本身
for (auto j : rer[i]) f[i] = max(f[i], f[j] + V[i]);//找反边，看看能从哪里转移而来
ans = max(ans, f[i]);//更新答案
}
cout << ans;
return 0;
}P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G
传送门
"牛牛 OJ"的题还是不错的。
容易发现，“喜欢”其实就是可达罢了。同样是因为 SCC 互相可达的性质，这题依旧可以缩点。
缩完点之后，我们可以保证最多只有一个“点”满足所有点均可达。因为如果存在两个点，那么就出现环了。
但是考虑到我们找这个“点”不是很方便，可以考虑到这个“点”的另外一个性质，那就是出度为
于是我们可以写出这个一份代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e4 + 10;
int n, m;
int Time, dfn[maxn], low[maxn], cnt, sccid[maxn], V[maxn];
stack<int>st;
vector<int>e[maxn], re[maxn];
void dfs(int i) {
dfn[i] = low[i] = ++Time;
st.push(i);
for (auto j : e[i]) {
if (!dfn[j]) dfs(j), low[i] = min(low[i], low[j]);
else if (!sccid[j]) low[i] = min(low[i], dfn[j]);
}
if (dfn[i] != low[i]) return;
++cnt;
while (true) {
int top = st.top();
st.pop();
sccid[top] = cnt, V[cnt]++;//统计一下一个SCC内有多少个节点
if (top == i) break;
}
}//板子
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1, u, v; i <= m; i++) {
cin >> u >> v;
e[u].push_back(v);
}
for (int i = 1; i <= n; i++) if (!dfn[i]) dfs(i);
for (int i = 1; i <= n; i++) for (int j : e[i]) {
if (sccid[i] == sccid[j]) continue;
re[sccid[i]].push_back(sccid[j]);//建边
}
for (int i = 1; i <= cnt; i++) if (re[i].size() == 0) cout << V[i];//出度为0直接输出
return 0;
}但是这样并不能直接 AC，我们犯了一个很容易忽视的细节，那就是出度为
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e4 + 10;
int n, m;
int Time, dfn[maxn], low[maxn], cnt, sccid[maxn], V[maxn];
stack<int>st;
vector<int>e[maxn], re[maxn];
void dfs(int i) {
dfn[i] = low[i] = ++Time;
st.push(i);
for (auto j : e[i]) {
if (!dfn[j]) dfs(j), low[i] = min(low[i], low[j]);
else if (!sccid[j]) low[i] = min(low[i], dfn[j]);
}
if (dfn[i] != low[i]) return;
++cnt;
while (true) {
int top = st.top();
st.pop();
sccid[top] = cnt, V[cnt]++;
if (top == i) break;
}
}//板子
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1, u, v; i <= m; i++) {
cin >> u >> v;
e[u].push_back(v);
}
for (int i = 1; i <= n; i++) if (!dfn[i]) dfs(i);
for (int i = 1; i <= n; i++) for (int j : e[i]) {
if (sccid[i] == sccid[j]) continue;
re[sccid[i]].push_back(sccid[j]);//建边
}
int sum = 0;
for (int i = 1; i <= cnt; i++) if (re[i].size() == 0) sum++;
if (sum > 1) cout << 0;//特判
else for (int i = 1; i <= cnt; i++) if (re[i].size() == 0) cout << V[i];
return 0;
}参考资料
《深入浅出》，《算法竞赛》，《信息学奥赛一本通》，《算法竞赛进阶指南》，OI-wiki，Link。
本文共计