linjunkai2024's blog
Tarjan 求强连通分量（SCC）与双连通分量（BCC）小记
linjunkai2024 LV 10 @ 2025-10-30 19:06:58

前言

据我所知，连通分量这个东西早就在我耳边回荡很久了，同时也是最让我头疼的算法之一。每次尝试学习 Tarjan 算法，都以失败告终。这一次，我要学会 Tarjan！

定义

“割”

割点：在无向图中，删去后使得连通分量数增加的点称为割点。
割边：在无向图中，删去后使得连通分量数增加的边称为割边，也称桥。

个人理解：就是将点或者边删掉使得连通块个数增加。

双连通

点双连通图：不存在割点的无向连通图称为 点双连通图。
边双连通图：不存在割边的无向连通图称为 边双连通图。
点双连通分量：一张图的极大点双连通子图称为 点双连通分量（V-BCC），简称点双。
边双连通分量：一张图的极大边双连通子图称为 边双连通分量（E-BCC），简称边双。

特别地，一个点为点双连通图和边双连通图，一条边也为点双连通图，但不是边双连通图。

强连通

强连通：有向图 G 强连通是指，G 中任意两个结点连通。
强连通分量（Strongly Connected Components，SCC）：极大的强连通子图。即无法变得更大的强连通子图。

注意！强连通是针对有向图的，不能对无向图使用“强连通”。

同样的，双连通是针对无向图的，不能对有向图使用“双连通”。

在实际问题中，可以利用强连通分量来缩点，将原图变成一个 有向无环图，利用拓扑排序降低时间复杂度或者简化题目。

DFS 生成树

下面~~直接把 OI-wiki 搬过来~~就是一棵 DFS 生成树。

有向图的 DFS 生成树主要有 $4$ 种边（不一定全部出现）：

树边（tree edge）：示意图中以黑色边表示，每次搜索找到一个还没有访问过的结点的时候就形成了一条树边。
反祖边（back edge）：示意图中以红色边表示（即 $7 \rightarrow 1$ ），也被叫做回边，即指向祖先结点的边。
横叉边（cross edge）：示意图中以蓝色边表示（即 $9 \rightarrow 7$ ），它主要是在搜索的时候遇到了一个已经访问过的结点，但是这个结点并不是当前结点的祖先。
前向边（forward edge）：示意图中以绿色边表示（即 $3 \rightarrow 6$ ），它是在搜索的时候遇到子树中的结点的时候形成的。

一些其他的

在所有 Tarjan 求连通分量的算法中都会用到一个栈（stack）来存储搜索树中尚未处理的结点。

还有在所有 Tarjan 求连通分量的算法中都会用到的两个数组：

$dfn_u$ ：表示在 dfs 的过程中当前结点 $u$ 第几个被访问到。
$low_u$ ：在 $u$ 的子树中能够回溯到的最早的已经在栈中的结点。我们会在 dfs 的过程中用 dp 的思想来更新 $low$ 。设 $u$ 子树的结点为 $v$ 。容易发现： $low_u$ 为结点 $v$ 与结点 $v$ 通过一条非树边能到的结点 $w$ 这两者 $dfn$ 的最小值。即 $low_u = \min(dfn_v, dfn_w)$ 。

接下来，正式介绍 Tarjan 算法。

先来讲 Tarjan 求强连通分量。

强连通分量

算法流程

首先，对于一个有向图，肯定要用 dfs 解决。废话

注意到对于父亲结点 $fa \rightarrow$ 儿子结点 $son$ ，有：

$dfn_{fa} < dfn_{son}$
$low_{fa} \ge low_{son}$

第一个结论很明显，第二个结论是因为 $son$ 的子树 $\subseteq$ $fa$ 的子树。

根据 $low$ 的定义和结论，我们可以对 $fa$ 和 $son$ 讨论三种情况：

$son$ 还未被访问过，所以我们接着往下进行 dfs。然后由于 $son$ 是在 $fa$ 的子树内的，我们可以用 $low_v$ 来更新 $low_u$ 。因为如果 $v$ 能回溯到的结点 $u$ 肯定也能回溯到。
$son$ 被访问过了，但不在栈中，此时就不需要对此结点进行操作了，因为 $u$ 都不在栈中了，证明它不需要进行更新了。
$son$ 被访问过了，但在栈中，此时根据 $low$ 的定义，我们可以用 $dfn_v$ 来更新 $low_u$ 。

对于一个连通分量图，显然只有一个结点 $u$ 满足 $low_u = dfn_u$ 。该结点一定是在 dfs 的过程中，该连通分量中第一个被访问过的结点，因为它的 $dfn$ 和 $low$ 值最小，不会被该连通分量中的其他结点所影响。

因此，在回溯的过程中，判定 $dfn_u = low_u$ 是否成立，如果成立，则栈中 $u$ 及其上方的结点构成一个 SCC。

Tarjan 算法的大致流程就说完了，接下来有些细节就直接上代码了。

code

void Tarjan(int u, int fa)
{
    low[u] = dfn[u] = ++cnt; // 初始是一个结点能回溯到的就是它自己
    stk.push(u), instk[u] = true; // 入栈，标记在栈内
    for (int v : e[u])
    {
        if (!dfn[v]) Tarjan(v), low[u] = min(low[u], low[v]); // 没访问过
        else if (instk[v]) low[u] = min(low[u], dfn[v]); // 访问过，在栈中
    }
    if (dfn[u] == low[u]) // 能构成一个 SCC
    {
        col[u] = ++scc; // col 代表当前节点属于哪一个 SCC
        while (stk.top() != u) // 还没有 pop 到当前结点，接着 pop
        {
            instk[stk.top()] = false; // 标记出栈
            stk.pop(); // pop
        }
        instk[u] = false; // 把当前节点也标记出栈
    }
}

边双连通分量

分析

注意到在无向图中删除一条边跟有向图中强连通类似，所以过程也跟求强连通分量类似，但是在面对我们的模板题时，出题人非常【数据删除】，没保证图是简单图，意味着有重边，可以往回走了，所以要对边编一个号。

模板题 code

#include <bits/stdc++.h>
#define ft first
#define sd second
#define endl '\n'
#define pb push_back
#define md make_pair
#define gc() getchar()
#define pc(ch) putchar(ch)
#define umap unordered_map
#define pque priority_queue
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 bint;
typedef pair<int, int> pii;
typedef pair<pii, int> pi1;
typedef pair<pii, pii> pi2;
const ll INF = 0x3f3f3f3f;
const db Pi = acos(-1.0);
inline ll read()
{
	ll res = 0, f = 1; char ch = gc();
	while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : f), ch = gc();
	while (ch >= '0' && ch <= '9') res = (res << 1) + (res << 3) + (ch ^ 48), ch = gc();
	return res * f;
}
inline void write(ll x)
{
	if (x < 0) x = -x, pc('-');
	if (x > 9) write(x / 10);
	pc(x % 10 + '0');
}
inline void writech(ll x, char ch) { write(x), pc(ch); }
const int N = 5e5 + 5;
int n, m;
int dfn[N], low[N], cnt; // 跟 SCC 一样
vector<pii> e[N];
vector<int> ans[N]; int bcc; // 答案
stack<int> stk;
void Tarjan(int u, int last) // last 上一条边
{
	low[u] = dfn[u] = ++cnt;
	stk.push(u);
	for (pii tmp : e[u])
	{
		int v = tmp.ft, edge = tmp.sd;
		if (edge == (last ^ 1)) continue; // 走的是相同的边
		if (!dfn[v]) Tarjan(v, edge), low[u] = min(low[u], low[v]);
		else low[u] = min(low[u], dfn[v]);
	}
	if (dfn[u] == low[u])
	{
		ans[++bcc].pb(u);
		while (stk.top() != u) ans[bcc].pb(stk.top()), stk.pop();
		stk.pop();
	}
}
int main()
{
	int n = read(), m = read();
	for (int i = 1; i <= m; i++)
	{
		int u = read(), v = read();
		e[u].pb(md(v, i * 2)), e[v].pb(md(u, i * 2 + 1)); // 给边编号
	}
	for (int i = 1; i <= n; i++) if (!dfn[i]) Tarjan(i, 0);
	writech(bcc, '\n');
	for (int i = 1; i <= bcc; i++)
	{
		writech(ans[i].size(), ' ');
		for (int j : ans[i]) writech(j, ' ');
		pc('\n');
	}
	return 0;
}

点双连通分量

点双连通分量就和前面两个有很大区别了。

性质

两个点双最多只有一个公共点，且一定是割点。
对于一个点双，它在 DFS 搜索树中 $dfn$ 值最小的点一定是割点或者树根。

算法主要过程

根据上面给出的第二个性质，我们可以对结点 $u$ 进行分类讨论：

$u$ 为割点，那么 $u$ 为点双连通分量的根。判断依据是：对于它的儿子结点 $v$ ，如果存在 $low[v] \ge dfn[u]$ 即 $u$ 不能回到祖先时，那么它为割点。但这种判断方式并不适用于 dfs 的出发点即 DFS 生成树的根，所以需要特判。
$u$ 为树根：
- 当 $u$ 的子树不唯一时，它为割点。
- 当 $u$ 的子树唯一时，它是一个点双连通分量的根。
- 当 $u$ 没有子树时，它自身就是一个点双连通分量。

模板题 & 好题解

模板题 code

#include <bits/stdc++.h>
#define ft first
#define sd second
#define endl '\n'
#define pb push_back
#define md make_pair
#define gc() getchar()
#define pc(ch) putchar(ch)
#define umap unordered_map
#define pque priority_queue
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 bint;
typedef pair<int, int> pii;
typedef pair<pii, int> pi1;
typedef pair<pii, pii> pi2;
const ll INF = 0x3f3f3f3f;
const db Pi = acos(-1.0);
inline ll read()
{
	ll res = 0, f = 1; char ch = gc();
	while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : f), ch = gc();
	while (ch >= '0' && ch <= '9') res = (res << 1) + (res << 3) + (ch ^ 48), ch = gc();
	return res * f;
}
inline void write(ll x)
{
	if (x < 0) x = -x, pc('-');
	if (x > 9) write(x / 10);
	pc(x % 10 + '0');
}
inline void writech(ll x, char ch) { write(x), pc(ch); }
const int N = 5e5 + 5;
vector<int> e[N], ans[N];
stack<int> stk;
int bcc, low[N], dfn[N], cnt;
void Tarjan(int u, int fa)
{
	dfn[u] = low[u] = ++cnt;
	stk.push(u);
	int son = 0; // 子树数量
	for (int v : e[u])
	{
		if (!dfn[v])
		{
			son++; // 子树 + 1
			Tarjan(v, u);
			low[u] = min(low[u], low[v]);
			if (low[v] >= dfn[u]) // 是割点
			{
				bcc++;
				while (stk.top() != v) ans[bcc].pb(stk.top()), stk.pop();
				ans[bcc].pb(u);
			}
		}
		else if (v != fa) low[u] = min(low[u], dfn[v]);
	}
	if (!fa && !son) ans[++bcc].pb(u); // 是出发点
}
void clear() { while (!stk.empty()) stk.pop(); } // 清空栈
int main()
{
	int n = read(), m = read();
	for (int i = 1; i <= m; i++)
	{
		int u = read(), v = read();
		e[u].pb(v); e[v].pb(u);
	}
	for (int i = 1; i <= n; i++) if (!dfn[i]) clear(), Tarjan(i, 0);
	writech(bcc, '\n');
	for (int i = 1; i <= bcc; i++)
	{
		writech(ans[i].size(), ' ');
		for (int j : ans[i]) writech(j, ' ');
		pc('\n');
	}
	return 0;
}

怎么感觉点双最难呢？

例题

P3387 【模板】缩点

题目传送门

分析

将原图缩成一个 DAG（有向无环图），然后可以用拓扑排序 dp 求出答案。时间复杂度 $\mathcal{O}(n + m)$ 。

code

#include <bits/stdc++.h>
#define ft first
#define sd second
#define endl '\n'
#define pb push_back
#define md make_pair
#define gc() getchar()
#define pc(ch) putchar(ch)
#define umap unordered_map
#define pque priority_queue
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 bint;
typedef pair<int, int> pii;
typedef pair<pii, int> pi1;
typedef pair<pii, pii> pi2;
const ll INF = 0x3f3f3f3f;
const db Pi = acos(-1.0);
inline ll read()
{
	ll res = 0, f = 1; char ch = gc();
	while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : f), ch = gc();
	while (ch >= '0' && ch <= '9') res = (res << 1) + (res << 3) + (ch ^ 48), ch = gc();
	return res * f;
}
inline void write(ll x)
{
	if (x < 0) x = -x, pc('-');
	if (x > 9) write(x / 10);
	pc(x % 10 + '0');
}
inline void writech(ll x, char ch) { write(x), pc(ch); }
const int N = 1e4 + 5, M = 1e5 + 5;
vector<int> e[N], ee[N]; // 新图 & 原图 
struct Edge {
	int u, v;
} edge[M]; 
int in[N]; // 入度 
int a[N], b[N]; // 原点权 & 新点权 
int dfn[N], low[N], cnt;
stack<int> stk; bool instk[N];
int col[N], scc; // 每个点属于哪一个 SCC 
void Tarjan(int u)
{
	dfn[u] = low[u] = ++cnt;
	stk.push(u), instk[u] = true;
	for (int v : e[u])
	{
		if (!dfn[v]) Tarjan(v), low[u] = min(low[u], low[v]);
		else if (instk[v]) low[u] = min(low[u], dfn[v]);
	} // 模板 
	if (low[u] == dfn[u])
	{
		col[u] = ++scc;
		while (stk.top() != u) col[stk.top()] = scc, instk[stk.top()] = false, b[scc] += a[stk.top()], stk.pop();
		b[scc] += a[u], instk[u] = false, stk.pop();
		// b += a：缩成一个点，将所有点的点权加起来 
	}
}
int dp[N];
void topo()
{
	queue<int> q;
	for (int i = 1; i <= scc; i++) if (!in[i]) q.push(i), dp[i] = b[i]; // 初始化 
	while (!q.empty())
	{
		int u = q.front(); q.pop();
		for (int v : ee[u])
		{
			dp[v] = max(dp[v], dp[u] + b[v]); // 更新 
			if (--in[v] == 0) q.push(v);
		}
	}
}
int main()
{
	int n = read(), m = read();
	for (int i = 1; i <= n; i++) a[i] = read();
	for (int i = 1; i <= m; i++) 
	{
		int u = read(), v = read();
		e[u].pb(v), edge[i] = {u, v};
	}
	for (int i = 1; i <= n; i++)
		if (!dfn[i])
		{
			while (!stk.empty()) stk.pop();
			Tarjan(i);
		}
	for (int i = 1; i <= m; i++)
		if (col[edge[i].u] != col[edge[i].v]) // 如果两个点不在同一个 SCC 
		{
			ee[col[edge[i].u]].pb(col[edge[i].v]); // 放进新图 
			in[col[edge[i].v]]++; // 入度 + 1 
		}
	topo(); // 拓扑排序 
	int ans = 0;
	for (int i = 1; i <= scc; i++) ans = max(ans, dp[i]); // 取最大值 
	write(ans); 
	return 0;
}

P3388 【模板】割点（割顶）

分析

由于这题只让我们求割点，所以我们只需要找到那些儿子回不到父亲的点即可。也就是删掉部分边，儿子回不来了。

code

#include <bits/stdc++.h>
#define ft first
#define sd second
#define endl '\n'
#define pb push_back
#define md make_pair
#define gc() getchar()
#define pc(ch) putchar(ch)
#define umap unordered_map
#define pque priority_queue
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 bint;
typedef pair<int, int> pii;
typedef pair<pii, int> pi1;
typedef pair<pii, pii> pi2;
const ll INF = 0x3f3f3f3f;
const db Pi = acos(-1.0);
inline ll read()
{
	ll res = 0, f = 1; char ch = gc();
	while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : f), ch = gc();
	while (ch >= '0' && ch <= '9') res = (res << 1) + (res << 3) + (ch ^ 48), ch = gc();
	return res * f;
}
inline void write(ll x)
{
	if (x < 0) x = -x, pc('-');
	if (x > 9) write(x / 10);
	pc(x % 10 + '0');
}
inline void writech(ll x, char ch) { write(x), pc(ch); }
const int N = 2e4 + 5;
int n = read(), m = read(), root;
int dfn[N], low[N], cnt;
int ans;
bool cut[N];
vector<int> e[N];
stack<int> stk;
void Tarjan(int u)
{
	low[u] = dfn[u] = ++cnt;
	int son = 0;
	for (int v : e[u])
	{
		if (!dfn[v])
		{
			son++;
			Tarjan(v);
			low[u] = min(low[u], low[v]);
			if (low[v] >= dfn[u] && u != root) ans += !cut[u], cut[u] = true; // 如果 v 到不了 u 并且 u 不是根 
		}
		else low[u] = min(low[u], dfn[v]); 
	}
	if (son > 1 && u == root) ans += !cut[u], cut[u] = true; // 不止一个子树并且 u 是根 
}
int main()
{
	for (int i = 1; i <= m; i++)
	{
		int u = read(), v = read();
		e[u].pb(v); e[v].pb(u);
	}
	for (int i = 1; i <= n; i++) if (!dfn[i]) root = i, Tarjan(i);
	writech(ans, '\n');
	for (int i = 1; i <= n; i++) if (cut[i]) writech(i, ' '); // 是割点 
	return 0;
}

P3469 [POI 2008] BLO-Blockade

分析

求割点练手题。

魏老师 Orz

code

#include <bits/stdc++.h>
#define ft first
#define sd second
#define endl '\n'
#define pb push_back
#define md make_pair
#define gc() getchar()
#define pc(ch) putchar(ch)
#define umap unordered_map
#define pque priority_queue
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 bint;
typedef pair<int, int> pii;
typedef pair<pii, int> pi1;
typedef pair<pii, pii> pi2;
const ll INF = 0x3f3f3f3f;
const db Pi = acos(-1.0);
inline ll read()
{
	ll res = 0, f = 1; char ch = gc();
	while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : f), ch = gc();
	while (ch >= '0' && ch <= '9') res = (res << 1) + (res << 3) + (ch ^ 48), ch = gc();
	return res * f;
}
inline void write(ll x)
{
	if (x < 0) x = -x, pc('-');
	if (x > 9) write(x / 10);
	pc(x % 10 + '0');
}
inline void writech(ll x, char ch) { write(x), pc(ch); }
const int N = 1e5 + 5;
int n = read(), m = read();
vector<int> e[N];
int dfn[N], low[N], cnt;
ll ans[N], siz[N];
// siz ：连通块大小 
void Tarjan(int u)
{
	low[u] = dfn[u] = ++cnt;
	siz[u] = 1; // 一个结点 
	ll remain = ans[u] = n - 1; 
	for (int v : e[u])
	{
		if (!dfn[v])
		{
			Tarjan(v);
			low[u] = min(low[u], low[v]); // 模板不会打，【】完了 
			siz[u] += siz[v];
			if (low[v] >= dfn[u]) ans[u] += (siz[v]) * (n - siz[v]), remain -= siz[v]; // 计算当前连通块的贡献 
		}
		else low[u] = min(low[u], dfn[v]);
	}
	// 所有判定 u 为割点的 v，它们的子树分别单独形成连通块，所以除掉这些 
	ans[u] += remain * (n - remain);
}
int main()
{
	for (int i = 1; i <= m; i++)
	{
		int u = read(), v = read();
		e[u].pb(v); e[v].pb(u);
	}
	Tarjan(1);
	for (int i = 1; i <= n; i++) writech(ans[i], '\n');
	return 0;
}

一些自己对自己的 Q & A

Q：为什么边双不需要记录在不在栈中？

A：因为无向边，肯定会在栈中。

后话

10K，大坑终于填完了。

希望我能对 Tarjan 算法求连通分量的理解能更深一步~~问候 Tarjan 祖宗和【数据删除】出题人~~。

Tarjan 求强连通分量（SCC）与双连通分量（BCC）小记

前言

定义

“割”

双连通

强连通

DFS 生成树

一些其他的

强连通分量

算法流程

code

边双连通分量

分析

模板题 code

点双连通分量

性质

算法主要过程

模板题 code

例题

P3387 【模板】缩点

分析

code

P3388 【模板】割点（割顶）

分析

code

P3469 [POI 2008] BLO-Blockade

分析

code

一些自己对自己的 Q & A

后话

Status

Development

Support

Tarjan 求强连通分量（SCC）与双连通分量（BCC）小记

前言

定义

“割”

双连通

强连通

DFS 生成树

一些其他的

强连通分量

算法流程

code

边双连通分量

分析

模板题 code

点双连通分量

性质

算法主要过程

模板题 code

例题

P3387 【模板】缩点

分析

code

P3388 【模板】割点（割顶）

分析

code

P3469 [POI 2008] BLO-Blockade

分析

code

一些自己对自己的 Q & A

后话

Status

Development

Support

Don't have an account?

SIGN IN