【集训整理】Tarjan算法 模板题

---

题面：

给你一个 n 个点，m* 条边的无向图简单图。求割点数量，割边数量，极大点双连通分量数量，极大点双连通分量包含边数的最大值。

割点：在图中移除这个点后，存在一个点对在原图中连通在新图中不连通。

割边：在图中移除这条边后，存在一个点对在原图中连通在新图中不连通。

点双连通分量：原图的一个点数大于 1 的连通子图，不存在对于这个子图的割点。

极大点双连通分量：是点双连通分量，且任意新增一个点后不是点双连通分量。

Tarjan主要基于dfs的思想，用来求解图的连通性问题。算法思想：

1. 时间戳：记录在dfs时每个截点被访问的顺序，用dfn[x]来表示。

2. 搜索树：从某个节点出发进行dfs，访问到的边和节点构成的树。

3. 追溯值：用low[x]表示，表示满足下列条件的节点中dfn的最小值：

   • x为根的搜索树中的所有节点

   • 通过一条不在搜索树上的边，能到达搜索树的节点

这样追溯值就表示x点属于包含low[x]节点的环（如果有环的话）。

追溯值的计算方法（dfs回溯的时候算）：

先让$low[x] = dfn[x]$，然后对x的每条边能到达的点y：

• 若y在x搜索树上（y>x)，则$low[x] = min(low[x],low[y])$

• 若y不在x的搜索树上（y<x），则$low[x] = min(low[x],dfn[y])$

桥

边(x,y)为桥当且仅当$dfn[x]<low[y]$

如果$low[y]<=dfn[x]$，说明有另一条路可以连回x以上，说明该边不是桥。

割点

点x是割点当且仅当$dfn[x]<=low[y]$

就算回路连回x点，删掉x点还是能把图拆断

参考代码：

void tarjan(int x){
	dfn[x]=low[x]=++num;
	int flag=0;
	for(int i=head[x];i;i=edge[i].next){
		int y=edge[i].to;
		if(!dfn[y]){
			tarjan(y);
			low[x]=min(low[x],low[y]);
			if(low[y]>=dfn[x]){
				flag++;
				if(x!=flag||flag>1){
					cur[x]=1;
				}
			}
		}
		else low[x]=min(low[x],dfn[y]);
	}
}

边双连通分量

定义：没有割边的分量

去掉桥后dfs即可

点双连通分量（vDCC）

在tarjan过程中维护一个栈:

当第一次访问一个节点时，将其入栈；当$dfn[x]<=low[y]$成立时（找到割点），一直弹栈直至y被弹出，x->y构成一个vDCC

参考代码：

void tarjan_dcc(int x){
	dfn[x]=low[x]=++num;
	stac[++top]=x;
	if(x==root&&head[x]==0){
		//孤立点
		dcc[++cnt].push_back(x);
		return ;
	}
	int flag=0;
	for(int i=head[x];i;i=edge[i].next){
		int y=edge[i].to;
		if(!dfn[y]){
			tarjan_dcc(y);
			low[x]=minn(low[x],low[y]);
			if(low[y]>=dfn[x]){
				flag++;
				if(x!=root||flag>1)cur[x]=1;
				cnt++;
				
				int z;
				do{
					z=stac[top--];
					dcc[cnt].push_back(z);
				}while(z!=y);

				dcc[cnt].push_back(x);
			}
		}
		else low[x]=minn(low[x],dfn[y]);
	}
}

强连通分量

注意点双是无向图的概念，强连通分量是有向图的概念。

与求点双的方法类似，但是强连通要求$dfn[x]==low[y]$时才能开始退栈。

参考

[tarjan算法(新) | Liyue (theshineyue.github.io)](https://theshineyue.github.io/2021/10/30/Tarjan 算法总结/)

60 分钟搞定图论中的 Tarjan 算法（一） - 知乎 (zhihu.com)