【图论基础】理解图的“闭环”：Tarjan 强连通分量算法全解析

• 🎓作者简介：CS专业的大一在校生
• 👨‍💻 博主主页：@Ahu_iii
• 📚 所属专栏：《基础算法》

1. 什么是强连通分量？

强连通分量（Strongly Connected Component，SCC）：在一个有向图中，如果任意两个顶点u和v，都可以互相到达（即u能到达v，且v也能到达u），那么我们称u和v是强连通的。

一个强连通分量就是一组极大集合（不能再扩展）里的点，满足集合中的任意两点都是强连通的。

2. 核心概念

Tarjan算法是基于DFS是实现，其中核心原理在于记录访问结点的时间戳并根据时间戳来调整所属SCC的编号,即low值。

其中最主要的”主角“有：

• 时间戳 dfn[u]：记录节点u第一次被访问的时间，就像给每个节点编号；
• low值low[u]：这是算法的灵魂！表示从节点u出发，能够回溯到的最早时间戳，也可看作当前所属SCC编号；
• 栈st：存储当前 DFS 路径上的节点；
• 入栈标记in_st[u]：标记节点是否在栈中；

2. 核心思想

想象你面前有着许多房间，部分房间之间是互通的：

• 你给每个房间（节点）按访问顺序编号（dfn）
• 每次你记录从当前房间能回到的最早房间编号（low）
• 你用绳子（栈）连接你走过的路径
• 当你发现从某个房间出发的所有路径都走完了，而且这个房间的low值等于它自己的编号时，说明找到了一个"出不去的区域"——这就是一个强连通分量。

3. 算法流程演示

最终结果：

这个过程就像解开一团毛线球，每当我们发现一个"结"（dfn == low）时，就能扯出一团完整的毛线（强连通分量）。

4. 算法模板

#include<iostream>
#include <vector>
#include <stack>
using namespace std;

const int MAXN = 1e5 + 10;
vector<int> g[MAXN];
int dfn[MAXN], low[MAXN], comp[MAXN];
bool in_st[MAXN];
int timer = 0, scc_cnt = 0;
stack<int> st;

void dfs(int u)
{
	dfn[u] = low[u] = ++timer;
	st.push(u);
	in_st[u] = true;
	
	for (int v : g[u])
	{
		if (!dfn[v])
		{
			dfs(v);
			low[u] = min(low[u], low[v]);
		}
		else if (in_st[v]) low[u] = min(low[u], dfn[v]);
	}

	if (dfn[u] == low[u])
	{
		++scc_cnt;
		while (1)
		{
			int x = st.top(); st.pop();
			in_st[x] = false;
			comp[x] = scc_cnt;      //记录scc编号
			if (x == u) break;
		}
	}
}

int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
	}

	for (int i = 1; i <= n; i++)   //避免遗漏不可达点
		if (!dfn[i]) dfs(i);


	for (int i = 1; i <= n; i++)
		cout << comp[i] << (i == n ? '\n' : ' ');

	return 0;
}

时间复杂度：$(n+m)$
空间复杂度：$O(n)$

常见应用场景：

• 缩点：将强连通分量缩成一个点，原来的有向图变成 DAG，便于进行拓扑排序等操作。
• 判断是否存在环：如果强连通分量的大小大于 1，说明存在环。

5. 实战例题

洛谷 P3387 【模板】缩点

题目描述

给定一个 $n$ 个点 $m$ 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。

允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。

输入格式

第一行两个正整数 $n,m$。

第二行 $n$ 个整数，其中第 $i$ 个数 $a_i$ 表示点 $i$ 的点权。

第三至 $m+2$ 行，每行两个整数 $u,v$，表示一条 $u\to v$ 的有向边。

输出格式

共一行，最大的点权之和。

输入输出样例 #1

输入 #1

2 2
1 1
1 2
2 1

输出 #1

2

说明/提示

对于 $100\%$ 的数据，$1\le n\le 10^4$，$1\le m\le 10^5$，$0\le a_i\le 10^3$。

• 2024-11-1 添加了 hack 数据；

解题思路

题目要求在图上DP求出一条权值和最大的路径，并说明可重复经过一条边或一个点，意味着同一SCC可直接所有点权值之和，即只需将同一scc的权值和看作一个点的权值再DP即可。

void solve() {
    // 1. 建图
    // 2. Tarjan 找强连通分量
    // 3. 缩点重新建图
    // 4. 在新图上 DP 求最大权值路径
}

完整代码

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

const int MAXN = 1e5 + 10;
vector<int> g[MAXN], dag[MAXN];
int w[MAXN], indeg[MAXN];
int dfn[MAXN], low[MAXN], scc_id[MAXN],scc_val[MAXN], tim = 0, scc_cnt = 0;
bool in_st[MAXN];
stack<int> st;
int dp[MAXN];			//dp[i]表示以 i 为终点的最大和

void tarjan(int u)
{
	dfn[u] = low[u] = ++tim;
	st.push(u);
	in_st[u] = true;

	for (int v : g[u])
	{
		if (!dfn[v])
		{
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if (in_st[v]) low[u] = min(low[u], dfn[v]);
	}

	if (dfn[u] == low[u])
	{
		++scc_cnt;
		while (1)
		{
			int x = st.top(); st.pop();
			in_st[x] = false;
			scc_id[x] = scc_cnt;
			scc_val[scc_cnt] += w[x];//将同一scc中的权值累加
			if (x == u) break;
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m;
	cin >> n >> m;

	for (int i = 1; i <= n; i++)
		cin >> w[i];
	
	for (int i = 0; i < m; i++)
	{
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
	}

	for (int i = 1; i <= n; i++)
		if (!dfn[i])
			tarjan(i);

	for(int u = 1; u <= n; u++)//建新图，scc编号看作结点
		for(int  v : g[u])
			if (scc_id[u] != scc_id[v])
			{
				dag[scc_id[u]].push_back(scc_id[v]);
				indeg[scc_id[v]]++;
			}
	
	queue<int> q;			// topo + dp按照路径顺序转移
	for (int i = 1; i <= scc_cnt; i++)
		if (!indeg[i])
		{
			dp[i] = scc_val[i];
			q.push(i);
		}

	while (!q.empty())
	{
		int u = q.front(); q.pop();

		for (int v : dag[u])
		{
			dp[v] = max(dp[v], dp[u] + scc_val[v]);
			if (!(--indeg[v]))
				q.push(v);
		}
	}

	int ans = 0;
	for (int i = 1; i <= scc_cnt; i++)//最后需要遍历一遍找出最大值
		ans = max(ans, dp[i]);

	cout << ans;
}

注：在缩点问题中，通常需要记录每个原结点属于哪个强连通分量，建议用scc_id[u]数组来记录结点u属于第几个强连通分量。

6. 总结与思考

Tarjan 强连通分量算法虽然看起来复杂，但其核心思想非常优雅：通过一次 DFS 遍历，利用时间戳和回溯信息，精准地识别出图中的所有"小团体"。
算法的精髓在于：

• dfn数组记录访问顺序;
• low数组记录能回溯到的最早节点;
• 栈维护当前搜索路径;
• dfn[u] == low[u]判定强连通分量的根;