Tarjan 求割点和桥

欢迎批评指正！

注意：本文只针对无向图。

前置芝士

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

Tarjan 求割点

设两个数组 $\mathit{dfn}$ 和 $\mathit{low}$，表示 dfs 序和至多通过 $1$ 条非树边所能到达的点的 $\mathit{dfn}$ 的最小值。

注意，这里的树边是有向边，是无向边中按 dfs 序访问的那个方向。非树边包含树边的反向边。
在 dfs 过程中维护这两个数组。

当 $u$ 和其儿子 $v$ 满足 $\mathit{low}_v\ge \mathit{dfn}_u$ 时，称 $u$ 是割点。

感性理解：因为这说明 $v$ 无法通过非树边“逃出”$u$ 的子树，只能通过 $u$，那么当 $u$ 被删除时，$v$ 就与其他点脱离了联系。

但有一个特例：如果 $u$ 是 dfs 树的根，那么只要有两个或更多儿子，$u$ 就是割点，因为删除根节点后这两个或更多子树将互不相连。

算法流程

dfs 到 $u$ 时：

• 给 $\mathit{dfn}_u$、$\mathit{low}_u$ 赋值。
• 遍历每个子节点 $v$：
  • 如果未被访问过，就先 dfs，然后更新 $\mathit{low}_u\gets\min(\mathit{low}_u,\mathit{low}_v)$。
  • 如果访问过，就更新 $\mathit{low}_u\gets\min(\mathit{low}_u,\mathit{dfn}_v)$。
  • 如果你想知道为什么这样更新，请看这个。
  • 如果满足 $\mathit{low}_v\ge \mathit{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;
}

Tarjan 求桥

求桥时，需要稍微修改 $\mathit{low}$ 的定义：那条非树边不得是树边的反向边（即不能从儿子走到父亲）。原因下面解释。

如果边 $(u,v)$ 满足 $\mathit{dfn}_u<\mathit{low}_v$，那么边 $(u,v)$ 是桥。

证明：

如果 $(u,v)$ 不是桥，那么根据桥的定义一定有另一条路径可使 $v$ 到达 $u$，而这只能通过走返祖边实现，于是 $\mathit{dfn}_u\ge \mathit{low}_v$，与条件相悖。

同时，因为 $(u,v)$ 在检查是否是桥的过程中应假设 $(u,v)$ 被删除，所以 $(u,v)$ 正走反走都不行，于是限定不能走树边的反向边，否则一个桥都找不到。

注意：重边不能忽略，因此在 dfs 时不能传父节点，应传父节点连过来的边。

算法流程

dfs 到 $u$ 时：

• 给 $\mathit{dfn}_u$、$\mathit{low}_u$ 赋值。
• 遍历每个子节点 $v$，如果 $(u,v)$ 不是来时的边：
  • 如果未被访问过，就先 dfs，然后更新 $\mathit{low}_u\gets\min(\mathit{low}_u,\mathit{low}_v)$。
    • 如果满足 $\mathit{low}_v>\mathit{dfn}_u$，将 $(u,v)$ 标记为桥。
  • 如果访问过，就更新 $\mathit{low}_u\gets\min(\mathit{low}_u,\mathit{dfn}_v)$。

代码

int n,m;
vector<pair<int,int>> e[21145];// 边表，pair存，.first 是连向的点的编号，.second 是边的编号
bitset<200008> cut;// 标记是否为桥

int edgecnt=1;
inline void addedge(int u,int v)
{
	e[u].push_back({v,edgecnt});
	e[v].push_back({u,edgecnt++});
}

int dfn[21145],low[21145],cnt=1,root;// cnt：时间戳，root：当前 dfs 树的根
void tarjan(int u=root,int pre=0)
{
	low[u]=dfn[u]=cnt++;
	for(pair<int,int> to:e[u])// 遍历所有孩子
	{
		if(to.second==pre)
		{
			continue;
		}
		int v=to.first;
		if(!dfn[v])// 若未遍历过
		{
			tarjan(v,to.second);
			low[u]=min(low[u],low[v]);// 更新 low
			if(low[v]>dfn[u])// 判断是否为桥
			{
				cut[to.second]=true;
			}
		}
		else
		{
			low[u]=min(low[u],dfn[v]);
		}
	}
	return;
}