# 【集训整理】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)](https://zhuanlan.zhihu.com/p/101923309)