Tarjan 算法学习笔记

（绝大部分都是贺的，来自 OI-WIKI 和 洛谷题解 ，自己抄一遍印象深刻一点，部分代码未编译，不保证正确性，但大体是对的）

一、DFS 生成树

注意可能有多棵，因为图可能不联通。

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

二、强连通分量

1.定义：

强连通：一个有向图，其任意一个节点都可以到达另一个节点。

强连通分量：一个有向图的极大强连通子图。

2.计算方法：

从一个节点开始，进行 DFS ，如果当前边指向一个已经经过的点，如果这条边是返祖边，则一定可以形成一个强连通分量。

3.数组含义：

dfn_x 代表 x 号节点的 dfn 序。

in_x 代表 x 号节点目前在不在栈里。

low_x 代表 x 号节点所在的强联通分量里 dfn 最小的节点的 dfn 是多少。

st_t 代表存储从搜索树上目前遍历到且不属于任何一个强连通分量的 t 个点的栈。

scc_x 代表 x 号节点所属的强连通分量的编号。

4.代码实现

void tarjan(int x){
　　dfn[x]=low[x]=++cnt;//计算 dfn 序，而且一开始只有 x ，所以 low = dfn 
　　in[x]=1;st[++t]=x;//入栈
　　for(int i=h[x];i;i=nxt[i])
　　 　if(!dfn[to[i]]){//没有遍历过，直接 dfs ，再更新 low 
　　　　 　tarjan(to[i]);
　　　　 　low[x]=min(low[x],low[to[i]]);
　　 　}else if(in[to[i]])low[x]=min(low[x],dfn[to[i]]);// to[i] 可能是 x 的祖先
　 if(low[x]==dfn[x]){
　  　　tot++;//新的强连通分量
　　　　while(st[t+1]!=x){
　　　　　　scc[st[t]]=tot;
　　　　　　in[st[t--]]=0;
　　　　}
　　}
}

三、割点

1.定义：

对于一个无向图，如果把一个点删除后这个图的极大连通分量数增加了，那么这个点就是这个图的割点。

2.计算方法：

① 对于 DFS 树的树根，它是割点当且仅当它有两个及以上的子树。

② 对于其它任意一个点，当且仅当以它为根的子树内没有向其它子树或祖先连边。

3.数组含义：

dfn_x 代表 x 号节点的 dfn 序。

low_x 代表以 x 号节点为根的子树里不经过 x 的路径能到达的 dfn 最小的节点的 dfn 是多少。

cut_x 代表 x 号节点是不是割点。

4.代码实现：

void tarjan(int x,int fa,int rt){
	dfn[x]=low[x]=++cnt;
	int c=0;//统计当 x=rt 时 x 的子树个数
	for(int i=h[x];i;i=nxt[i]){
		if(!dfn[to[i]]){
			tarjan(to[i],x,rt);
			low[x]=min(low[x],low[to[i]]);
			if(low[to[i]]>=dfn[x]&&x!=rt)cut[x]=1;//条件②
			if(x==rt)c++;
		}else if(to[i]!=fa)low[x]=min(low[x],dfn[to[i]]);//更新 low
	if(c>=2&&x==rt)cut[x]=1;//条件①
}

 三、割边

1.定义：对于一个无向图，如果删掉一条边后图中的连通分量数增加了，则称这条边为桥或者割边。

2.计算方法：

首先，容易知道割边一定是 DFS 树的树边。记录 DFS 树上指向 x 的边，它是割边当且仅当以 x 为根的子树内没有向其它子树或祖先连边。

不用考虑 x 是否是根节点。

注意因为用 链式前向星 存图，所以一次只能存一个方向的边，所以可以让 cnt 从 2 开始，如果当前边编号为 i ，则其反向边编号为 i^1 。

3.数组含义：

dfn_x 代表 x 号节点的 dfn 序。

low_x 代表以 x 号节点为根的子树里不经过搜索树上指向 x 的那条边的路径能到达的 dfn 最小的节点的 dfn 是多少。

cut_i 代表 i 号边是不是割边。

4.代码实现：

void tarjan(int x,int van){//记录连向 x 的边（请忽略变量名） 
	dfn[x]=low[x]=++cnt;
	for(int i=h[x];i;i=nxt[i])
		if(!dfn[to[i]]){
			tarjan(to[i],i);
			low[x]=min(low[x],low[to[i]]);
			if(dfn[x]<low[to[i]])cut[i]=cut[i^1]=1;//条件，注意是 > 不是 >= ，因为研究的是从 x 出发的边 i 
　　　　　　　　　　　　　　　//如果 dfn[x]=low[to[i]] ，则说明下面有点能连回 x ,那么去掉 i 后以 to[i] 为根的子树与 x 仍联通， i 不为割边
		}else if(i!=(van^1))low[x]=min(low[x],dfn[to[i]]);//更新 low
}

四、点双连通分量（代码、计算方法是贺 洛谷 UID=434929 的）

1.定义：

点双连通：在一张连通的无向图中，对于两个点 u 和 v ，如果无论删去哪个点（只能删去一个，且不能删 u 和 v 自己）都不能使它们不连通，我们就说 u 和 v 点双连通。

点双连通不具有传递性。

性质：两个不同的点双连通分量最多有一个公共点，否则它们可以合成为一个更大的点双连通分量。

2.计算：

对于一个点双，它在 DFS 搜索树中 dfn 值最小的点一定是割点或者树根。

如果该点双不包含割点或树根，它一定可以继续拓展。所以我们在点双中任取一个割点或者树根。

①如果该点是树根，它的 dfn 值是整棵树里最小的。它若有两个以上子树，那么它是一个割点；它若只有一个子树，它一定属于它的直系儿子的点双，因为包括它；它若是一个独立点，视作一个单独的点双。

②当这个点是割点时，它所属的点双必定不可以向它的父亲方向包括更多点，因为一旦回溯，它就成为了新的子图的一个割点，不是点双。所以它应该归到其中一个或多个子树里的点双中。

3.数组含义：

dfn_x 代表 x 号节点的 dfn 序。

low_x 代表 x 号节点所在的点双联通分量里 dfn 最小的节点的 dfn 是多少。

st_t 代表存储从搜索树上目前遍历到且还可以属于其它点双连通分量的 t 个点的栈。

bcc 代表 x 号节点所属的点双连通分量的编号（这里用 ans 记录了）。

4.代码实现：

void tarjan(int x,int fa){
	int son=0;//为孤点或根节点统计子树个数 
	dfn[st[++t]=x]=low[x]=++cnt;//进栈、初始化 
	for(int i=h[x];i;i=nxt[i])
		if(!dfn[to[i]]){
			son++;tarjan(to[i],x);
			low[x]=min(low[x],low[to[i]]);
			if(low[to[i]]>=dfn[x]){//情况②， x 是割点，则有一个从 x 开始的点双连通分量 
				bcc++;//点双个数增加 
				while(st[t+1]!=to[i])ans[bcc].push_back(st[t--]);//退栈、记录 
				ans[bcc].push_back(x);
			}
		}else if(to[i]!=fa)low[x]=min(low[x],dfn[to[i]]);//更新 low 
	if(fa==0&&son==0)ans[++bcc].push_back(x);//情况①，处理孤点或根节点统计子树个数 
}

五、边双连通分量（代码、计算方法是贺 洛谷 UID=425694的）

1.定义：

在一张连通的无向图中，对于两个点 u 和 v，如果无论删去哪条边（只能删去一条）都不能使它们不连通，我们就说 u 和 v 边双连通。

 边双连通具有传递性，即，若 x、y 边双连通，x、z 边双连通，则 y、z 边双连通。

2.计算方法：

把图中所有割边去掉就行。因为如果一个边双有割边，去掉之后一定不连通。

3.数组含义：

dfn_x 代表 x 号节点的 dfn 序。

low_x 代表以 x 号节点为根的子树里不经过搜索树上指向 x 的那条边的路径能到达的 dfn 最小的节点的 dfn 是多少。

cut_i 代表 i 号边是不是割边。

dcc_x 记录了 x 所在的边双连通分量的编号。

4.代码实现：

void dfs(int x,int num){
	dcc[x]=num;//记录所在变双编号 
	ans[num].push_back(x);
	for(int i=h[x];i;i=nxt[i])
		if(!dcc[to[i]]&&!cut[i])dfs(to[i],num);
	//如果没被填色并且连的边不是割边就标记为同一块 
}
void tarjan(int x,int van){//求割边的板子 
	dfn[x]=low[x]=++cnt;
	for(int i=h[x];i;i=nxt[i])
		if(!dfn[to[i]]){
			tarjan(to[i],i);
			if(dfn[x]<low[to[i]])cut[i]=cut[i^1]=1;
			low[x]=min(low[x],low[to[i]]);
		}else if(i!=(van^1))low[x]=min(low[x],dfn[to[i]]);
}

六、动态树

听说好像也是 Robert E. Tarjan 发明的，但是本蒟蒻不会。

七、结语

本蒟蒻贺了一晚上，希望大家能看懂（当然我这个主要还是为了自己整理），记得给原作者点赞。

所有的 Tarjan 主要就是维护 dfn 和 low 数组，再用 st 记录一下值。本质都很像，学会举一反三。