Tarjan 学习笔记

技术分享 8个月前 (03-17) 0 999+

声明：标准的 Tarjan 是判断有用的横叉边和返祖边时使用 (low_x = min(low_x,dfn_v))，但是，经过我和豆包以及 deepseek 唇枪舌剑般的辩论之后，证明判断有用的横叉边和返祖边时使用 (low_x = min(low_x,low_v)) 也没有问题，并且更加直观，好理解。

一、问题引入

当你要求割点/割边/点双连通分量/边双连通分量/强连通分量的时候，它们都可以用一个算法来解决，而且代码差别不大，这个算法就是 Tarjan。

二、什么是强连通分量

对于一张有向图 (S) 的子图 (V)，满足 (V) 内的点两两之间可达，并且不存在一个子图 (G) 使得 (G supseteq V,G not= V)，通俗的讲就是无法继续扩张的两两可达的子图。

三、Tarjan 求强连通分量算法推导

首先对于一个有向图的搜索树中，它分为4种边：树边、返祖边、横叉边、前向边。树边就是搜索树中正常的边，返祖边就是一个点返回它的祖先的一条边，横叉边就是一个点连向了一个不是它的祖先也不是它的后代的点的这样一条边，前向边就是一个点连向它的后代（并非儿子）的边。

然后就是算法的流程，这个算法有两个数组 (dfn) 和 (low)，分别表示当前点的 (operatorname{dfs}) 序和当前点所能到达的最小的 (dfn)，就跟并查集有点像，Tarjan 里的 (low) 数组就类似并查集里的 (f) 数组，首先根据搜索树的特性，对于任何一个强连通分量它们的点集在搜索树上的 (dfn) 是连续的，而且你会发现，任何一个强连通分量都有一个制高点 (x)（类似并查集找图的连通块时的根），使得 (low_x = x)，也就相当于找到了并查集中一个连通块的根，于是我们就有了一个大胆的猜想，先准备一个栈，存放着所有点，我们先在搜索时求出 (low) 数组和 (dfn) 数组，搜索时如果发现 (low_x = x)，说明找到了一个强连通分量的制高点，将强连通分量的数量加 (1)，同时将这个强连通分量从栈里删掉。

但是，我们会面临一个问题：如何求 (low)（(dfn) 是好求的）？

你可能会立马想到在搜索时，使用：

low[x] = min(low[x],low[v]);

来求出 (low)，但是你会发现，这样不一定能得到正确的 (low)，因为你可能爸爸更新了，但儿子没法及时更新，但是……

真的有必要求出正确的 (low) 吗？

其实没必要。

因为我们的 (low) 它的作用其实只是找出强连通分量的制高点，也就是判断 (low_x) 是否等于 (dfn_x)，所以就算我们的 (low) 无法实时更新出正确的答案也不影响我们找到每个强连通分量的制高点。

然后再说一下，在搜索中遇到返祖边或目前没有被划入任何一个强连通分量的横叉边（前向边没用，因为指向的点已经被划分了）就不需要搜索，直接使用上述语句更新 (low)，如果是普通的树边就先搜索然后再更新 (low)，其它情况就什么都不用做。

四、Tarjan 求强连通分量板子

代码很简单，重要部分就几行。

#include<bits/stdc++.h> using namespace std; const int N = ;//这里是数组大小，根据题目数据范围定 vector<int>a[N];//边集 vector<int>g[N];//存每个强连通分量 int cnt,scc_cnt,top;//分别表示目前的dfs序、当前找到几个强连通分量，栈顶 int dfn[N],low[N];//跟上面说的dfn和low一样 int scc_color[N];//表示每个点属于第几个强连通分量 int sta[N];//栈 void dfs(int x) { 	dfn[x] = low[x] = ++cnt;//先求出dfn，然后先给每个low赋一个初值 	sta[++top] = x;//放入栈 	for(int v:a[x]) 	{ 		//上面说的更新low的方法 		if(!dfn[v]) 		{ 			dfs(v); 			low[x] = min(low[x],low[v]); 		} 		else if(!scc_color[v]) 		{ 			low[x] = min(low[x],low[v]); 		} 	} 	if(dfn[x] == low[x])//找到制高点 	{ 		scc_cnt++;//强连通分量数量+1 		int u; 		do 		{ 			u = sta[top--];//取出栈顶 			scc_color[u] = scc_cnt;//标记所属强连通分量编号 			g[scc_cnt].push_back(u);//在这个点所属的强连通分量里放入这个点 		} 		while(u!=x);//因为对于任何一个强连通分量它们的点集在搜索树上的dfn是连续的，所以说从这个强连通分量的制低点（栈顶一定是这个强联通分量的制低点，这个原理很简单吧）删到制高点后就不能继续删了 	} } int vis[N]; signed main() { 	int n,m; 	scanf("%d %d",&n,&m); 	for(int i = 1;i<=m;i++) 	{ 		int x,y; 		scanf("%d %d",&x,&y); 		a[x].push_back(y);//连边 	} 	for(int i = 1;i<=n;i++) 	{ 		if(!dfn[i])//因为图不一定连通，所以得将所有的连通块都搜一遍 		{ 			dfs(i); 		} 	} 	//根据题目要求决定输出什么 	return 0; }

注意：这只是板子，应用时请随机应变。

五、Tarjan 求强连通分量的缩点技巧

有一些题目需要将每个强连通分量缩成一个点，才能变得更好处理，码量也会更好写，同时会变得更加直观、好理解。

所以说我们先用 Tarjan 求出强连通分量，然后将所有边的两端不在同一个强连通分量的边保留即可。

代码：

vector<int>e[N]; int x[N],y[N]; for(int i = 1;i<=m;i++) { 	if(scc_color[x[i]]!=scc_color[y[i]]) 	{ 		e[scc_color[x[i]]].push_back(scc_color[y[i]]); 	} }

(x,y) 数组表示每条边的两端，(e) 数组表示缩点后的边集。

缩点后只有强连通分量的数量个点。

六、Tarjan 求强连通分量例题

B3609 [图论与代数结构 701] 强连通分量

此题就是求强连通分量的板子题，直接套板子即可。
由于题目要求很特殊，我们需要准备一个 (vis) 数组，表示输出时当前点是否已经被输出过。
代码：

#include<bits/stdc++.h> using namespace std; const int N = 1e4+5; vector<int>a[N]; vector<int>g[N]; int cnt,scc_cnt,top; int dfn[N],low[N]; int scc_color[N]; int sta[N]; void dfs(int x) { 	dfn[x] = low[x] = ++cnt; 	sta[++top] = x; 	for(int v:a[x]) 	{ 		if(!dfn[v]) 		{ 			dfs(v); 			low[x] = min(low[x],low[v]); 		} 		else if(!scc_color[v]) 		{ 			low[x] = min(low[x],low[v]); 		} 	} 	if(dfn[x] == low[x]) 	{ 		scc_cnt++; 		int u; 		do 		{ 			u = sta[top--]; 			scc_color[u] = scc_cnt; 			g[scc_cnt].push_back(u); 		} 		while(u!=x); 		sort(g[scc_cnt].begin(),g[scc_cnt].end());//按题目要求点编号进行排序 	} } int vis[N]; signed main() { 	int n,m; 	scanf("%d %d",&n,&m); 	for(int i = 1;i<=m;i++) 	{ 		int x,y; 		scanf("%d %d",&x,&y); 		a[x].push_back(y); 	} 	for(int i = 1;i<=n;i++) 	{ 		if(!dfn[i]) 		{ 			dfs(i); 		} 	} 	printf("%dn",scc_cnt); 	for(int i = 1;i<=n;i++) 	{ 		//按照题目要求输出 		if(vis[i]) 		{ 			continue; 		} 		for(int x:g[scc_color[i]]) 		{ 			vis[x] = 1; 			printf("%d ",x); 		} 		printf("n"); 	} 	return 0; }

P3387 【模板】缩点

由于可以重复经过点，但权值只计算一次，并且是有向图，所以我们可以先缩点，然后就变成了一个不能重复经过点的有向图，求路径边权和最大值，很容易发现可以用拓扑排序求出答案。
代码：

#include<bits/stdc++.h> using namespace std; const int N = 1e5+5; vector<int>a[N]; int cnt,scc_cnt,top; int dfn[N],low[N]; int scc_color[N]; int sta[N]; vector<int>e[N]; int x[N],y[N]; int dep[N]; int q[N]; int val[N]; int f[N]; int s[N]; void dfs(int x) { 	dfn[x] = low[x] = ++cnt; 	sta[++top] = x; 	for(int v:a[x]) 	{ 		if(!dfn[v]) 		{ 			dfs(v); 			low[x] = min(low[x],low[v]); 		} 		else if(!scc_color[v]) 		{ 			low[x] = min(low[x],low[v]); 		} 	} 	if(dfn[x] == low[x]) 	{ 		scc_cnt++; 		int u; 		do 		{ 			u = sta[top--]; 			scc_color[u] = scc_cnt; 		} 		while(u!=x); 	} } signed main() { 	int n,m; 	scanf("%d %d",&n,&m); 	for(int i = 1;i<=n;i++) 	{ 		scanf("%d",&val[i]); 	} 	for(int i = 1;i<=m;i++) 	{ 		scanf("%d %d",&x[i],&y[i]); 		a[x[i]].push_back(y[i]); 	} 	for(int i = 1;i<=n;i++) 	{ 		if(!dfn[i]) 		{ 			dfs(i); 		} 	} 	for(int i = 1;i<=n;i++) 	{ 		s[scc_color[i]]+=val[i]; 	} 	for(int i = 1;i<=scc_cnt;i++) 	{ 		f[i] = s[i]; 	} 	for(int i = 1;i<=m;i++) 	{ 		if(scc_color[x[i]]!=scc_color[y[i]]) 		{ 			e[scc_color[x[i]]].push_back(scc_color[y[i]]); 			dep[scc_color[y[i]]]++; 		} 	} 	int h = 1,t = 0; 	for(int i = 1;i<=scc_cnt;i++) 	{ 		if(!dep[i]) 		{ 			q[++t] = i; 		} 	} 	while(h<=t) 	{ 		int x = q[h++]; 		for(int v:e[x]) 		{ 			f[v] = max(f[v],f[x]+s[v]); 			dep[v]--; 			if(!dep[v]) 			{ 				q[++t] = v; 			} 		} 	} 	int maxx = 0; 	for(int i = 1;i<=scc_cnt;i++) 	{ 		maxx = max(maxx,f[i]); 	} 	printf("%d",maxx); 	return 0; }