Tarjan 学习笔记

Creeper_l · 2023-08-25 19:35:23 · 个人记录

这里讲一下 tarjan 算法。主要包括有向图的强连通分量，无向图的边双连通分量与点双连通分量以及缩点。

有向图的强连通分量

首先我们需要了解几个定义。（以下说法均针对有向图）

连通分量：在一个块中，任意两个点之间能够互相到达。即 u 能到 v，v 也能到 u。

强连通分量（简称 SCC）：极大的连通分量。这里的极大是指，再加入图中的任意一个点，该块都不是一个连通分量。

知道这两个概念之后，我们就来考虑如何求一张有向图中的所有强连通分量。这就需要 tarjan 算法了。

首先，tarjan 算法是按照 dfs 序来遍历的，也就是深度优先搜索顺序。在遍历的过程中的一条边 u 到 v，有以下四种名称：

• 树枝边：u 是 v 的父亲节点。

• 前向边：u 是 v 的祖先节点。

• 后向边：v 是 u 的祖先节点。

• 横叉边：v 是已经搜索过的子树上的一个点。

这四种边本质上没有什么用，有助于理解。

接下来定义两个时间戳（记录 dfs 序的时间）数组 dfn 和 low。dfn_{i} 表示深度优先遍历到点 i 时的时间是多少，low_{i} 表示从点 i 往后遍历，能遍历到的 dfn 值最小的点的 dfn 值是多少。

根据时间戳的定义，我们可以发现这四种边的一些性质，证明显然：

• 树枝边：dfn_{u}<dfn_{v}

• 前向边：dfn_{u}<dfn_{v}

• 后向边：dfn_{u}>dfn_{v}

• 横叉边：dfn_{u}>dfn_{v}

然后考虑如何判断强连通分量。假设我们要找的都是强连通分量的最上面的那一个点，那么当 dfn_{u}=low_{u} 的时候，则点 u 一定是强连通分量的最上面的点。

为什么？大概感性理解一下。在有向图中当 dfn_{u}=low_{u} 的时候，意味着从 u 出发无法走到 u 的祖先节点。假设点 u 不是强连通分量的最上面的点，又已知从 u 出发无法走到 u 的祖先节点，这就与强连通分量的定义相矛盾，所以得证。

如何维护两个时间戳呢，其实很简单。dfn 数组很好维护，只需要在函数开头更新就行了。那 low 数组呢？如果 v 点已经被遍历过且还在在栈里，那就直接用 v 点的 dfn 值去更新 u 点的 low 值；否则就用 tarjan 去遍历点 v，再用点 v 的 low 值去更新点 u 的 low 值。

最后的问题就在于如何将每一个强连通分量全部找出来。我们可以维护一个栈来实现。遍历每个点的时候立即进栈，当点 u 满足上述条件的时候，循环弹出栈顶元素直到栈顶元素为 u。弹出来的每一个点都属于当前的强连通分量。证明过程比较复杂。

这样我们就找到了图中的每一个强连通分量。

而这种算法的最终目的一般是缩点，即把每一个强连通分量变成一个点（不一定需要重新建图）。这样原来的有向图就变成了一个有向无环图。而且还有一个很重要的性质，缩点后的点的编号的倒序一定是它的拓扑序，就不需要再写一遍拓扑排序了。这使我们做题方便了很多，比如所缩点后可以 O(n+m) 求最短路，还可以简化很多问题。

Code

inline void Tarjan(int u)
{
    dfn[u] = low[u] = ++timestamp;
    stk.push(u),in_stack[u] = true;
    for(int i = head[u]; ~ i;i = e[i].nxt)
    {
        int now = e[i].v;
        if(!dfn[now]){Tarjan(now);low[u] = min(low[u],low[now]);}
        else if(in_stack[now]) low[u] = min(low[u],dfn[now]);
    }
    if(dfn[u] == low[u])
    {
        ++scc_cnt;int y;
        do
        {
            y = stk.top();stk.pop();
            id[y] = scc_cnt;
            in_stack[y] = false;
        }while(y != u);
    }
}

练习题：

P3387 【模板】缩点

P1262 间谍网络

P4742 [Wind Festival] Running In The Sky

P2002 消息扩散

无向图的边双连通分量

在了解边双连通分量之前，先要引入一个桥（割边）的概念。

首先，桥指的是一条边。在一个无向图中，桥的定义是：如果删去该条边，则整个图会变得不连通。

边双连通分量（简称DCC）：一个极大地不包含桥的连通块。这里极大是指，再添加图中的任意一个节点，该连通块中就会包含桥。

边双连通分量的 tarjan 算法和有向图的强连通分量非常相似，有些步骤简述。

首先考虑如何判断桥，时间戳的定义不变。对于一条边 u v，如果 low_{v} > dfn_{u}，那么这条边就一定是桥。因为点 v 无论如何也走不到点 u 以及点 u 上面的点，如果将这条边删去，无向图一定会被分成上下两个部分，也就是说整个图不连通了。所以这条边一定是桥。

那如何找边双连通分量呢？当 dfn_{u}=low_{u} 的时候，点 u 一定是该边双连通分量的最高点。首先可以证明这个块一定是连通的，很显然，因为栈中元素肯定是被遍历过的。然后证明这个块一定是最大的，因为 dfn_{u}=low_{u}，即点 v 无论如何也走不到点 u 以及点 u 上面的点，所以如果加入一个点，这个块一定不连通了，于是得证。

用栈来维护，方法与有向图的强连通分量相似。

Code

inline void tarjan1(int u,int from)
{

    dfn[u] = low[u] = ++timestamp;
    s.push(u);
    for(int i = head[u]; ~ i;i = e[i].nxt)
    {
        int now = e[i].v;
        if(!dfn[now]) 
        {
            tarjan1(now,i),low[u] = min(low[u],low[now]);
            if(dfn[u] < low[now]) is_bridge[i] = is_bridge[i ^ 1] = true;
        }
        else if(i != (from ^ 1)) low[u] = min(low[u],low[now]);
    } 
    if(dfn[u] == low[u])
    {
        ++dcc_cnt;int y;
        do
        {
            y = s.top();s.pop();
            id[y] = dcc_cnt;
        }while(y != u);
    }
}

练习题：P8436 【模板】边双连通分量

无向图的点双连通分量

我感觉点双连通分量是这三个中间最难得一个了，中间还需要分类讨论，显得很繁琐。而且很不符合直觉。

首先引入一个割点的概念。割点表示的是一个点，对于一个无向图来说，割点指：如果删去该点，整个图会变得不连通。

点双连通分量（简称 DCC）：一个极大地不包含割点的连通块。这里极大是指，再添加图中的任意一个节点，该连通块中就会包含割点。

先来考虑如何找割点。这里需要用到分类讨论：如果点 u 不是根节点，那么当 dfn_{u} <= low_{u} 时，点 u 是割点；如果点 u 是根节点，那么只要 u 有两个及以上的儿子节点，那么点 u 是割点。

证明：如果点 u 不是根节点，因为 dfn_{u} <= low_{now}，即从点 u 出发无法走到点 now 上面的点，所以如果删去点 u,整个快会变得不连通。所以点 u 是割点；如果点 u 是根节点，则有性质：点 u 上面一定没有点了。又已知 u 有两个及以上的儿子节点，所以如果删去点 u，那么 u 的两颗子树一定会不连通，所以点 u 是割点。于是得证。

接下来考虑如何找点双连通分量，对于一条边 u v，如果 dfn_{u}<=low_{v}，那么点 u 就是点双连通分量的最上面的点，证明略。但是这里要注意一个细节，就是不能立刻把点 u 从栈中弹出，因为点 u 还可能在另外一个点双连通分量中。所以只能在do while 循环外面再将点 u 加入当前点双连通分量中。但是还要考虑一个特殊情况，就是只有一个孤立点，也就是当点 u 是根节点并且它没有儿子节点的时候，它自己本身就是一个点双连通分量，放在 tarjan 函数最后特判。

最后有一点需要注意，点双连通分量需要在循环内维护，因为每个点可能对应多个点双连通分量。

和点双联通分量相关的知识叫圆方树，具体内容看我这篇博客。

还有一个很重要的性质要讲：即同一个点双中的两不同点 u,v 之间一定存在一条简单路径经过给定的在同一个点双内的另一点 w，证明略，可以去看 oiwiki。

对割点的一个很神奇的理解：两个点双连通分量中唯一的交点，如果想从一个点双连通分量出去（到另外一个点双连通分量），必须通过割点

Code

inline void Tarjan(int u,int father)
{
    dfn[u] = low[u] = ++timestamp;
    s.push(u);int son = 0;
    for(int i = head[u]; ~ i;i = e[i].nxt)
    {
        int now = e[i].v;
        if(!dfn[now])
        {
            Tarjan(now,u);low[u] = min(low[u],low[now]);
            son++;
            if(dfn[u] <= low[now])
            {
                dcc_cnt++;int y;
                do
                {
                    y = s.top();s.pop();
                    dcc[dcc_cnt].push_back(y);
                }while(y != now);
                dcc[dcc_cnt].push_back(u);
            } 
        }
        else if(now != father) low[u] = min(low[u],dfn[now]);
    }
    if(u == root && son == 0) dcc[++dcc_cnt].push_back(u); 
}

练习题：

P8435 【模板】点双连通分量

P3388 【模板】割点（割顶）