Tarjan学习笔记

· · 题解

0 前言

tarjan 算法并不仅仅是一种算法，其中神秘的思想与逻辑令人惊叹。

由于笔者太弱，在此只展示 tarjan 算法求割点的方式。

1 正儿八经的算法简介

Tarjan 算法是基于深度优先搜索的算法，用于求解图的连通性问题。

Tarjan 算法可以在线性时间内求出无向图的割点与桥，进一步地可以求解无向图的双连通分量；同时，也可以求解有向图的强连通分量、必经点与必经边。

2 前置知识

1 割点

割点的定义是：对于一张联通图 G = (V,E)，存在一个点 x \in V，删除所有与 x 相关联的边后，图分裂成两个或两个以上的不联通的子图，x 即为图 G 的割点。

听不懂是吧，我也不懂，对于初学者，我们只需要知道：删掉割点和与其相连的边之后，图不联通了。

2 时间戳

时间戳是一种对点进行编号的一种方式，具体是在深度优先搜索时，统计每个点第一次进入的时间。

3 搜索树

在图 G 中选择 n 个点，n-1 条边所构成的一颗树，选择方式为深度优先搜索。

3 关于追溯值

这是 tarjan 算法中最神奇的东西，也是初学者最难理解的地方，我会尽量以清晰易懂的方式讲解。

在此，先给出 lyd 在《算法竞赛进阶指南》中给出的定义：

设以 x 为根的搜索树的子树为 \text{subtree}(x)，x 的追溯值 \text{low}(x) 定义为以下节点的时间戳的最小值:

是不是很晕？我也晕。 我们结合例图来理解一下。

图中用红色标出的边为树边，对于 6 号节点，它的 \text{low} 就是 1，因为它可以通过图中用奇怪颜色标出的非树边（我们也称这两条边为返祖边） (2,6),(1,6) 到达 1,2，而 1,2 中最小的时间戳是 1。所以 \text{low}(6) = 1。

接下来考虑 \text{low} 的计算方法，自己肯定可达，所以 \text{low}(x) = \text{dfn}(x)。

然后考虑与 x 的连边 (x,y)

4 如何求割点

tarjan 算法告诉我们：如果 y 是 x 的子节点且 \text{low}(y) \geq \text{dfn}(x)，那么 x 就是割点。

由定义，y 在不经过 (x,y) 的情况下只能到达比 x 更晚访问到的节点，所以删去 (x,y) 后，y 必定与比 x 更早访问到的点不相连，就必然会分裂成一张不联通的子图。

但是：对于根节点，我们显然发现，这样是行不通的。如下图：

我们如果钦定 1 为根，显然按照上面的判定方法，1 是割点。但是显然的，1 并不符合割点的定义，所以，我们引出对于根 s 的判定方法：

5 代码实现

void tarjan(int x,bool root){
    int ch = 0;
    low[x] = dfn[x] = ++tot;//初始化
    for(int i = head[x];i;i = e[i].nxt){
        int y = e[i].to;
        if(!dfn[y]){//在搜索树上
            tarjan(y,0);//先递归
            low[x] = min(low[x],low[y]);//求low
            if(low[y] >= dfn[x] && !root) ans[x] = 1;//判定方式1
            if(root) ch ++;//判定方式2
        }
        else low[x] = min(low[x], dfn[y]);//求low
    }
    if(root && ch >= 2){//判定方式2
        ans[x] = 1;
        return ;
    }
    return ;
}

本文码字时间共计 2h，如果您觉得不错，可以点个赞支持一下。

如果您有任何不懂的地方，欢迎私信询问。谢谢！