割点 Tarjan 算法

最近学习图论,写篇题解记录一下。

定义

  • 对于一个无向图,如果把一个点删除后这个图的极大连通分量数增加了,那么这个点就是这个图的割点(又称割顶)。

这篇博客主要介绍,Tarjan 算法用于求 割点。

割点

Tarjan 算法,记录 节点访问时间戳 dfn,节点能够回溯到的最早的点的时间戳 low

对于某一点:

  1. 如果这个点是根节点,且有两个以上与它相连的连通分量,那这个点就是割点。
  2. 如果某个点后继是一个连通分量,而这个点不是根节点,那这个点是割点。

第一种情况

我们需要记录根节点 fa,在遍历的时候,如果重复访问到了 fa,说明找到了 fa 下面的一个连通分量。

第二种情况

设当前点 s,对于访问的下一个节点 y

如果 low[y] >= dfn[s],说明这个点下面有一个连通分量。

注:这里类似于 Tarjan 求 SCC 时,我们所做的 min(low[s],dfn[y])

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void tarjan(int s, int fa){
dfn[s] = low[s] = ++cc;
int child = 0;
for(int i = head[s]; i!=-1; i=NDS[i].next){
int y = NDS[i].to;
if(!dfn[y]){
tarjan(y,fa);
low[s] = min(low[s], low[y]); // 回溯后更新
if(low[y]>=dfn[s] && s != fa) // 情况 2
cut[s] = 1;
if(s==fa) // 情况 1 计数
child++;
}
low[s] = min(low[s], dfn[y]);
}
if(child>=2&&s==fa){
cut[s] = 1; // 情况 1
}
}