【笔记】图论-Tarjan 算法

Tarjan 是一种求强连通分量、双连通分量的常用算法，其拓展例如求缩点、割点、割桥以及 2-SAT 等都是非常实用的。

这篇文章主要讲一下 Tarjan 的朴素算法及其在缩点、求割点等方面的应用（~~主要是因为其他的都不会了 QAQ~~）

什么是强连通分量？

在有向图 G 中，如果两个顶点 vi,vj 间（vi>vj）有一条从 vi 到 vj 的有向路径，同时还有一条从 vj 到 vi 的有向路径，则称两个顶点强连通。如果有向图 G 的每两个顶点都强连通，称 G 是一个强连通图。有向图的极大强连通子图，称为强连通分量。——来自某度的解释

什么意思呢？

就是说在一个有向图中，有一个或几个子图，从它们中的任何一个点都可以到另外的任意一个点，这个子图就被称为是强连通分量（一个点也可以被称作是强连通分量哦）

另外，这张子图一定要是最大的，即要把所有满足条件的点全部加进这张子图，才能称为是强连通分量。

举个例子：

举个栗子

在这张图中， $1,2,3,4$ 和 $5$ 还有 $6$ 是三个强连通分量，但 $1,3,4$ 并不能被称为是强连通分量，因为它不是最大的满足条件的子图，必须要加入点 2 才算。

简单介绍 Tarjan 算法

Tarjan 算法是一种基于 DFS（深度优先搜索）的求图的强连通分量的算法，非常常用（~~还有就是活在《信奥一本通》上的 Kosaraju 和活在百度百科中的 Gabow 算法~~），同时，其时间复杂度为 $O(n)$ ，算是非常优秀的了。

一些变量

tot：当前点是第几个被遍历的。
dfn[]：记录每个点是第几个被遍历的，可以理解为一个时间戳。
low[]：记录每个点不经过祖先节点能到达最早的祖先的时间戳（下称”返祖“~~好名字~~）。

PS: 这里大部分人写的都是能到达的最早的祖先，但这样就和下面有一个公式不符，所以我改了一下，如果不对希望大佬在评论里指出，谢谢！
stack[]：一个栈，存放强连通分量（不是直接存哦，有一些方法的）。
vis[]：标记每个点是否在栈中。
color[]：记录每个点属于第几个强连通分量。
p[]：记录每个强连通分量有几个点。（最后这两个都是缩点时用的）

算法思路

从一个点出发，遍历整张图。
dfn[] 数组初始化为当前点（下称 u）被遍历的顺序，同时将 u 入栈。
初始化 low[u]=dfn[u]，因为一个点一定能到达它自己。
枚举所有出边（链式前向星存图），如果这条边到达的点（下称 v）还没有被遍历过，则遍历点 v，然后更新 low[u]，公式为：

$low[u]= \min (low[u],low[v])$

因为点 v 能到达的祖先节点，点 u 也一定能到达（废话），所以应该更新点 u 的 low 值。

如果 v 已被遍历过，且 v 在栈中，也要更新 low 值公式为：

$low[u]= \min (low[u],dfn[v])$

因为到达之前到过的点（也就是祖先），说明这个点可以返祖，那么肯定是要更新 low 值的（更详细的请看下面的“一些可能的问题”）
枚举完所有出边后，如果 $dfn[u]=low[u]$ 则说明这个点是一个强连通分量的开始点（~~梦开始的地方~~）它不可能属于其他任何一个强连通分量，因为它无法返祖，所以不可能和之前的点组成一个强连通分量，因而它属于一个独立的强连通分量，这时，将栈中在这个点之后入栈的点全部出栈（包括这个点），因为这些点也不属于其他任何一个强连通分量，如果属于，那么 u 就不可能无法返祖，所以，它们都是同一个强连通分量。

看起来很麻烦是不是？~~我也觉得~~下面用图来手模一下就清楚了。

上图：

~~资源缺乏，凑合着看吧~~

我们从点 1 开始遍历，下面是模拟过程：

从点 1 开始！ $u=1,dfn[1]=1,low[1]=1,stack=\{1\},vis[1]=1$ ，先遍历点 3。
$u=3,dfn[3]=2,low[3]=2,stack=\{1,3\},vis[3]=1$ ，再遍历点 5。
$u=5,dfn[5]=3,low[5]=3,stack=\{1,3,5\},vis[5]=1$ ，遍历点 6。
$u=6,dfn[6]=4,low[6]=4,stack=\{1,3,5,6\},vis[6]=1$ ，此时没有出边了，开始硬核出栈。
检测到 $dfn[6]=low[6]$ ，将栈中点 6 及其之后的点全部出栈（其实只有一个点）， $stack=\{1,3,5\},vis[6]=0$ ， $6$ 为一个强连通分量。
回溯到点 5，没有出边了，出栈。 $stack=\{1,3\},vis[5]=0$ ， $5$ 为一个强连通分量。
回溯到点 3，遍历点 4。
$u=4,dfn[4]=5,low[4]=5,stack=\{1,3,4\}vis[4]=1$ ，接下来遍历点 1，发现已经遍历过了，说明点 4 返祖了（！！！），此时更新 $low[4]=dfn[1]=1$ 。再遍历点 6，发现点 6 已经遍历过了，但又不在栈中，说明点 6 不属于点 4 所在的强连通分量，所以不管。此时所有出边枚举完了，回溯到点 3。
更新 $low[3]=\min(low[3],low[4])=1$ （意思是点 3 能到达点 1），没有出边了，回溯到点 1。
遍历点 2， $u=2,dis[2]=6,low[2]=6,stack=\{1,3,4,2\},vis[2]=1$ ，枚举出边，只有一个点 4 已经被遍历了，且点 4 在栈里， $low[2]=\min(low[2],dfn[4])=5$ ，枚举完毕，回溯。
点 1 出边枚举完毕，开始出栈，stack 清空，vis 清空， $1,3,4,2$ 为一个强连通分量。自此，遍历完毕，三个强连通分量全部被求出（~~完结撒花，感谢陪伴~~）。

一些可能的问题

Q：如果这张有向图不连通怎么办？也就是说，如果从一个点出发不能遍历完整张图怎么办？

A：废话，那就从点 1 枚举到点 n，如果当前点没有被遍历过，就从这一点开始遍历。

Q：如何判断当前点有没有被遍历过？

A： dfn 数组是干嘛的？记录每个点被遍历的顺序啊！如果 dfn 数组不为 0，则表示它已经被更新，也被遍历过了。

Q：还是没有搞懂为什么遍历完一个点后要把 low 更新为当前点和这条边的终点的 low 值中的较小值啊。

A： low 数组记录的是能到达的最早的祖先，既然这条边的终点能到达，那起点肯定也能到达啊，同时要取最早的祖先，所以要取较小的值。

Q：既然许多大佬都说 low[] 是记录能到的最早的祖先，那为什么出现”返祖“情况时不取祖先的能到达的最早时间戳，而要取祖先的时间戳呢？换句话说，为什么遍历到被遍历过的又在栈里的点（就是祖先嘛）时不用公式 $low[u]= \min (low[u],low[v])$ ，而要用公式 $low[u]= \min(low[u],dfn[v])$ 呢？

A：这个问题其实有点复杂，理论上来说用前者是绝对没有问题的（仅限于求强连通分量的时候），但后面在求割点时，第一个公式就会出 bug，所以我将 low[] 数组定义为不经过祖先节点能到达的最早祖先，详细情况请看后面讲求割点的部分。

（大概就是这些了，如果还有什么问题后面再补充）

参考代码

题目： 洛谷 P2863 [USACO06JAN] 牛的舞会 The Cow Prom

传送门

（PS：我没有用 P2341 【模板】强连通分量 / [HAOI2006] 受欢迎的牛，是因为这道题虽然写的是强连通分量的模板，但其实还用到了缩点的知识，不便于朴素算法的理解）

题目大意： 求子图内点的个数大于 1 的强连通分量个数。

代码：

#include<cstdio>
#include<cstring>
#define min(a,b) a<b?a:b
using namespace std;
struct Edge//链式前向星存图
{
	int next;
	int to;
};
Edge edge[50001];
int n,m,s,head[10001];
int cnt,k,ans,dfn[10001],low[10001],stack[10001],v[10001];//我这里的代码时间和这篇笔记的时间隔了将近 5 天
                                                          //所以有些变量名可能不太一样
                                                          //这里 v 数组就是上面的 vis
                                                          //cnt 是上面的 tot
void tarjan(int x)
{
	cnt++;
	dfn[x]=low[x]=cnt;
	stack[++k]=x;
	v[x]=1;//初始化各种数组，包括 dfn 和 low 初始化为 x 被遍历到的次序，x 入栈，v 标记 x 入栈
	for(int i=head[x];i!=-1;i=edge[i].next)
		if(!dfn[edge[i].to])//如果没有搜过
		{
			tarjan(edge[i].to);
			low[x]=min(low[x],low[edge[i].to]);//取自己能到的最早祖先和终点能到的最早祖先
		}
		else
			if(v[edge[i].to])//如果搜过了，且这个点在栈里，说明返祖了
				low[x]=min(low[x],dfn[edge[i].to]);//详情见上面
	if(dfn[x]==low[x])//如果 dfn[x]=low[x]，说明这个点为整个强连通分量中的最老的祖先，也说明整个强连通分量已经遍历完了
	{
		int flag=0;
		while(stack[k]!=x)
		{
			flag=1;
			v[stack[k]]=0;
			k--;
		}
		v[x]=0;
		k--;
		if(flag)//这里是判断这个强连通分量点的个数是否大于 1（题目要求）
			ans++;
	}
}
void add_edge(int u,int v)
{
	edge[s].next=head[u];
	edge[s].to=v;
	head[u]=s;
	s++;
}
int main()
{
	memset(head,-1,sizeof(head));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		add_edge(a,b);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])
			tarjan(i);//不确定从一个点开始就能遍历完整张图，所以要每个点都试一下
	printf("%d",ans);
	return 0;
}

Tarjan+缩点

What means 缩点？

一张有向图中，如果存在环，就会造成很多不方便的地方，比如不方便进行动归计算，这时，就可以用缩点来解决问题，所谓缩点，就是将这张有向图中所有的强连通分量变成一个一个的团，然后给这些团加边，形成一张 DAG（有向无环图），就便于解决问题了。

这张图会让你更明白一些：

这张图中共有四个强连通分量，已经用红色圈出来了，对其进行缩点操作以后，就会变成下面这个样子：

~~是不是很棒棒啊~~仔细研究一番以后，可以发现：点 1 对应强连通分量 $1,2,3,4$ ，点 2 对应强连通分量 $8,9$ ，点 3 对应强连通分量 $5,6,7$ ，点 4 对应强连通分量 $10$ ，此时，这张图中已经不存在环了，可以放心地尽情搞♂事♂情。

算法思路

Tarjan 求出强连通分量，并在出栈时更新 color 和 p。
遍历所有边，如果这条边连接的两个点不在同一个强连通分量中，就连边。

看起来很简单是不？没错，就是这么简单，没有别的了，只是有些细节可以再优化一下，下面的代码中会讲到。

参考代码

题目： 洛谷 P3387 【模板】缩点

传送门

题目大意： 将一张有向图缩点，然后在新的图上跑一遍记忆化 DFS（DP 也行），求出一条经过的点权值和最大的路径。

为什么知道这道题是缩点呢？~~废话这题目写了是缩点模板的嘛~~

既然题目告诉我们，可以重复经过一个点或一条边，但权值只计算一次，那么，既然是同一个强连通分量，取了一个，为什么不能取其他的呢？反正可以重复经过，取完一个强连通分量再回到之前的点就行了，完全不影响啊，这样缩完点后，一个强连通分量就是一个点，到达这个点，相当于就是到达了整个强连通分量，同时，在 DAG 图上跑记忆化，可以做到 $O(n)$ 啊，如果不缩点，那就要重复经过一个点，这样时间复杂度就大大提升了，所以为什么不先用 Tarjan 跑一遍 $O(n)$ ，再用记忆化跑一遍 $O(n)$ 呢，这样更优啊。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct Edge
{
	int next;
	int to;
};
Edge edge[100001];
int x[100001],y[100001]; 
int n,m,s,a[10001],head[10001];
int cnt,cur,top,dfn[10001],low[10001],stack[10001],v[10001];//cur 是统计强连通分量个数的
int np[10001],b[10001];//这里的 np 相当于是上面的 p，b 则是 color
int ans,f[10001];//f[i] 记录的是从第 i 个强连通分量开始遍历所能取到的最大值
void add_edge(int u,int v)
{
	edge[s].next=head[u];
	edge[s].to=v;
	head[u]=s;
	s++;
}
void tarjan(int x)
{
	cnt++;
	dfn[x]=low[x]=cnt;
	stack[++top]=x;
	v[x]=1;
	for(int i=head[x];i!=-1;i=edge[i].next)
		if(!dfn[edge[i].to])
		{
			tarjan(edge[i].to);
			low[x]=min(low[x],low[edge[i].to]);
		}
		else
			if(v[edge[i].to])
				low[x]=min(low[x],dfn[edge[i].to]);
	if(dfn[x]==low[x])
	{
		cur++;//当前强连通分量遍历完毕，cur 加一
		while(stack[top+1]!=x)//这里之所以用 top+1 是为了把 x 也弹出来
		{
			v[stack[top]]=0;
			b[stack[top]]=cur;//标记栈顶的点属于第 cur 个强连通分量
			np[cur]+=a[stack[top]];//p 为这一强连通分量中所有点权值之和
			top--;
		}
	}
}
void dfs(int x)
{
	if(f[x])
		return;//搜过了，就不再搜了
	int maxn=np[x];
	for(int i=head[x];i!=-1;i=edge[i].next)
	{
		if(!f[edge[i].to])
			dfs(edge[i].to);
		maxn=max(maxn,f[edge[i].to]+np[x]);//取所有出边的终点中 f 的最大值
	}
	f[x]=maxn;
}
int main()
{
	memset(head,-1,sizeof(head));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&x[i],&y[i]);
		add_edge(x[i],y[i]);//优化：将之前的边存下来，便于后面重新建图
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])
			tarjan(i);
	memset(head,-1,sizeof(head));
	memset(edge,0,sizeof(edge));
	s=0;
	for(int i=1;i<=m;i++)//为什么不用链式前向星遍历：为了节省内存，我们将之前的 edge 清空
                         //因为链式前向星不是线性存图，所以一边遍历 edge 一边用 edge 来存图会冲突
		if(b[x[i]]!=b[y[i]])//b[x[i]] 和 b[y[i]] 分别表示 x[i] 和 y[i] 所在的强连通分量
			add_edge(b[x[i]],b[y[i]]);//添加第 b[x[i]] 个强连通分量和第 b[y[i]] 个强连通分量之间的边
	for(int i=1;i<=cur;i++)//缩点后的图不一定从一点出发就能到达所有的点，因此要一个一个枚举
	{
		dfs(i);//记忆化深搜
		ans=max(ans,f[i]);
	}
	printf("%d",ans);
	return 0;
}

Tarjan+割点

何为割点？

在一张无向图中，有一个或几个点，删去之后整张图就不连通了，这样的点称为割点，也就是说，如果没有这个点，一张连通图就会变成几张连通图。

还是举个例子：

举个栗子

在这张无向图中，很容易看出，如果删去点 3，整张图就会变成 $1,2$ 和 $4,5,6$ 两张连通图，因此，点 3 为这张无向图的割点，同时，如果删去点 4，整张图会变成 $1,2,3$ 和 $5,6$ 两张连通图，因此，点 4 也是这张图的割点。

算法思路

从一个根节点出发，遍历全图。
一边遍历，一边判断当前点是否为割点。

关于如何判断割点，我们分成两部分来考虑。
1. 如果这个点是根节点，那好办，如果它连接两个及以上的连通图，这个点就是割点，因为如果去掉这一点，这些连通图就不连通了（之所以会有两张及以上的连通图，就是因为这些图彼此两两不连通，而只通过根节点连接彼此，所以，如果根节点炸了，这些图就失去了唯一的连通途径，就不连通了）
2. 如果这个点不是根节点，就要判断它下面的点不通过它能否返祖，如果全都可以，则这个点不为割点，因为它的儿子都可以不通过它返祖，那要它也没什么用，但只要有一个儿子必须经过它才能返祖，这个点就是割点，因为去掉它后它的儿子就不能与上面的图连通。
  
  如何判断？
  
  用这个！ $if(low[v]\ge dfn[u])$ ，low 记录的是不经过祖先节点所能访问到的最早的祖先的时间戳，如果儿子的 low 值比当前节点的时间戳要小（或正好等于它），就说明这个儿子不经过它，是无法访问到更早的点的，所以去掉这个点后，它的儿子和祖先节点的连接就会断掉，就不连通了，所以这个点是割点。
  
  用图来模拟一下好了。
  
  我们从点 1 开始遍历，因此点 1 为根节点，它连接了两张连通图（即 $2,3,4$ 和 $5$ ），如果它炸了，两张连通图就不再相互连通，所以它是割点。再看点 2，因为点 3 和点 4 不经过点 2 就无法访问点 1，所以，点 2 如果炸了，点 3 和点 4 就不能与点 1 连通，所以点 2 也是割点。

一个非常重要的地方

这里就可以看出为什么当遍历时遇到祖先节点时的公式为 $low[u]=\min(low[u],dfn[v])$ 而不是 $low[u]=\min(low[u],low[v])$ 了，因为如果是后者的话则计算的是不管怎样到，总之能到达的最早的祖先，这样无法判断这个点最直接的能回到的祖先，也就无法判断割点。在上面的图中，如果用后面那个公式，low[3] 和 low[4] 就都会变成 1，此时再判断点 2，就不能看出点 2 是割点了。

参考代码

题目： 洛谷 P3388 【模板】割点（割顶）

传送门

题目大意： 求一张无向图中的割点（注意：是从小到大输出节点！）

参考代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct Edge
{
	int next;
	int to;
};
Edge edge[200001];
int n,m,s,head[20001];
int cnt,top,cur,dfn[20001],low[20001],stack[20001],v[20001],b[20001];//b 用来存放割点
void add_edge(int u,int v)
{
	edge[s].next=head[u];
	edge[s].to=v;
	head[u]=s;
	s++;
}
void tarjan(int x,int root)//root 是当前连通图的根节点，也就是最先被遍历的那个点
{
	int son_cnt=0,flag=0;//son_cnt 统计连接的连通图个数
	cnt++;
	dfn[x]=low[x]=cnt;
	stack[++top]=x;
	v[x]=1;
	for(int i=head[x];i!=-1;i=edge[i].next)
		if(!dfn[edge[i].to])
		{
			tarjan(edge[i].to,root);
			low[x]=min(low[x],low[edge[i].to]);
			if(low[edge[i].to]>=dfn[x]&&x!=root)
				flag=1;
			if(x==root)
				son_cnt++;//遍历完一个点后，这个点所在的连通图也就遍历完了，所以加一
		}
		else
			if(v[edge[i].to])
				low[x]=min(low[x],dfn[edge[i].to]);//注意！原因上面讲过了，不这样写的话就会 WA
	if(son_cnt>=2)//如果连接的连通图个数大于一，则这个点为割点
		flag=1;
	if(flag)
		b[++cur]=x;
	if(dfn[x]!=low[x])
		while(stack[top+1]!=x)
		{
			v[stack[top]]=0;
			top--;
		}
}
int main()
{
	memset(head,-1,sizeof(head));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add_edge(x,y);
		add_edge(y,x);//无向图要添加两条边
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])
			tarjan(i,i);//枚举所有点，如果没有被遍历过，就从这一点开始遍历
	sort(b+1,b+1+cur);//排序！！
	printf("%d\n",cur);
	for(int i=1;i<=cur;i++)
		printf("%d ",b[i]);
	return 0;
}