割点 Tarjan 算法

发表于 分类于 阅读次数： Waline： 本文字数： 748

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

定义

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

这篇博客主要介绍，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
    }
}