Tarjan 求割点和桥

Charged Creeper 的小窝 / 2023-08-29 / 原文

欢迎批评指正！

前置芝士

割点：对于一个点 \(u\)，若删除 \(u\) 会使当前无向图中连通分量增多，我们就称 \(u\) 为该图的割点。
桥（割边）：同理，对于一条边 \((u,v)\)，若删除 \((u,v)\) 会使当前无向图中连通分量增多，我们就称 \((u,v)\) 为该图的桥。
Tarjan 求强连通分量

Tarjan 求割点

设两个数组 \(dfn\) 和 \(low\)，表示 dfs 序和仅通过 \(1\) 条非树边所能到达的点的最小 \(dfn\)。
注意，这里的树边是有向边。
在 dfs 过程中维护这两个数组。

当 \(u\) 和其儿子 \(v\) 满足 \(low_v\ge dfn_u\) 时，称 \(u\) 是割点。
感性理解：因为这说明 \(v\) 无法通过非树边“逃出”\(u\) 的子树，只能通过 \(u\)，那么当 \(u\) 被删除时，\(v\) 就与其他点脱离了联系。
但有一个特例：如果 \(u\) 是 dfs 树的根，那么只要有两个或更多儿子，\(u\) 就是割点，因为删除根节点后这两个或更多子树将互不相连。

算法流程

dfs 到 \(u\) 时：

给 \(dfn_u\)、\(low_u\) 赋值。
遍历每个子节点 \(v\)：
- 如果未被访问过，就先 dfs，然后更新 \(low_u=\min(low_u,low_v)\)。
- 如果访问过，就更新 \(low_u=min(low_u,dfn_v)\)。
- 如果你想知道为什么这样更新，请看这个。
- 如果满足 \(low_v\ge dfn_u\)，将 \(u\) 标记为割点。但要特判根节点。

代码

int n,m;
vector<int> e[21145];// 边表
bitset<20008> cut;// 标记是否为割点

int dfn[21145],low[21145],cnt=1,root;// cnt：时间戳，root：当前 dfs 树的根
void tarjan(int u=root)
{
	int chd=0;// 孩子数量
	low[u]=dfn[u]=cnt++;
	for(int v:e[u])// 遍历所有孩子
	{
		if(!dfn[v])// 若未遍历过
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);// 更新 low
			if(low[v]>=dfn[u])// 判断是否为割点
			{
				cut[u]=true;
			}
			chd++;
		}
		else
		{
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(u==root)// 特判是否为根节点
	{
		if(chd>=2)
		{
			cut[u]=true;
		}
		else
		{
			cut[u]=false;
		}
	}
	return;
}