# 【集训整理】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)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blog.mcyou.cc/suan-fa-xiang-guan/suan-fa/ji-xun-zheng-li-tarjan-suan-fa-mu-ban-ti.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.