【学习笔记】Tarjan 算法 | 宇宙よりも遠い場所

March 18, 2019

【学习笔记】Tarjan 算法

这次,我想用尽量简明的语言,来记录一下 Tarjan 算法的学习。

本文篇幅较长,完整阅读大约需要 15-20 分钟。

0x00 Tarjan 算法的用途

当我们接触到一个新的算法的时候,首先要知道它的适用场景。Tarjan 是图论中一个重要的算法。对于无向图,Tarjan 算法能在 $O(n)$ 的时间内,求出无向图的割点割边,进而求出无向图的双连通分量;对于有向图,Tarjan 算法能够求出有向图的强连通分量必经点与必经边

0x01 概念

割点与割边(桥)

给定无向图 $G=(V, E)$:

割点:若对于点 $x \in V$,从 $G$ 中删去 $x$ 及与 $x$ 相连的边之后,$G$ 分成了两个以上不相连的子图,那么 $x$ 称为图 $G$ 的割点。
割边(桥):若对于边 $e \in E$, 从 $G$ 中删去边 $e$ 后,$G$ 分裂成两个不相连的子图,那么 $e$ 称为图 $G$ 的割边(或桥)。

简而言之,割点与割边可以理解为沟通两张不相连的图,使它们成为一张图的枢纽

割点与割边

搜索树

在图 $G=(V,E)$ 中,任选顶点 $x$ 作为起点对整张图进行 DFS,每个点只访问一次——此时,每个节点最多有一条入边 $e_{x}$ ,所有在 DFS 过程中经过的边,就构成无向图的搜索树。如果 DFS 的时候遇到了多个分支,我们总是走最左边的那个分支。

时间戳(aka. DFS 序)

节点 $i$ 的时间戳(或 DFS 序)是节点在图的 DFS 中被访问的顺序,也就是说深度优先遍历一张图的时候,$i$ 节点是第 $t$ 个被访问的节点,那么 $i$ 的 DFS 序就是 $t$, 记作 $dfn[i] = t$.

DFS序

追溯值

追溯值是个比较难理解的东西。在我们对整张图进行 DFS 的过程中,正在访问中的节点会加入一个栈 $s$ 中,节点 $i$ 追溯值的意义是:从节点 $i$ 或其子搜索树中的节点出发,能够追溯到的正在 DFS 栈 $s$ 中的节点序号。而我个人认为比较能理解接受的意义是:从节点 $i$ 出发,除了走通向 $x$ 的父节点 $p$ 的边 $(p, x)$ 之外,能到达的 dfn 最小的节点的序号。

追溯值

在上图中,考虑节点 2 的追溯值。因为节点 5 可以通过一条不在搜索树上的边到达节点 1,因此 $low[5] = dfn[1] = 1$. 而 5 是 4 的子节点,4 是 3 的子节点……层层向上回溯,最终有 $low[2] = low[3] = low[4] = low[5] = 1.$.

考虑节点 7 的追溯值,因为 7 没有子节点也没有出边,所以 $low[7]$ 只能等于 $dfn[7] = 7$.

考虑节点 6 的追溯值,因为节点 9 可以通过一条不在搜索树上的边到达节点 6,因此 $low[9] = dfn[6] = 6$, 层层回溯最终有 $low[6] = low[8] = low[9] = 6$.

节点 $i$ 的追溯值我们用 $low[i]$ 表示。根据定义,我们计算 $low[i]$ 的方法如下:

  1. 初始化,首先令 $low[i] = dfn[i]$
  2. 考虑 $i$ 的每条出边(不包括通向 $i$ 的父节点的出边)$(i, j)$,如果 $j$ 是 $i$ 在搜索树上的子节点,那么 $low[i] = min(low[i], low[j])$
  3. 如果 $j$ 不是 $i$ 在搜索树上的子节点,也不是 $i$ 的父节点,说明 $j$ 不在搜索树上,那么 $low[i] = min(low[i], dfn[j])$
  4. $low[i]$ 应该在 DFS 回溯之前计算,确保 $low[j]$ 在 $low[i]$ 前被计算。

(无向图)双连通分量

点双连通图:不存在割点的图;边双连通图:不存在割边(桥)的图。

点双连通分量 (v-DCC, vertex double connected component): 无向连通图的极大点双连通子图。通俗地讲,就是从一个无向图中选出最多的 $n$ 个点,这些点及其连边构成的图不含有割点,删去 $n$ 个点中的任意一个,其它点仍然连通,图不会分割成多张子图。

类似地,定义边双连通分量(e-DCC, edge double connected component): 无向连通图的极大边双连通子图。通俗地讲,就是从一个无向图中选出最多的 $n$ 个点及在这些点之间连的 $m$ 条边,构成一张新图,这张新图不含有割边,删去 $m$ 条边中的任意一条,其它点仍然连通,图不会分割成多张子图。

v-DCC 和 e-DCC 统称为双连通分量。注意双连通分量的定义是“极大”的。

缩点

e-DCC 的缩点:设无向图 $G$ 中有多个边双连通分量 $G_{e1}, G_{e2}, …, G_{en}$,把每个 e-DCC 视为独立的节点 $i_{1}, i_{2}, …, i_{n}$, 把两个 e-DCC 间的割边 $(x, y)$看做连接两个独立节点的边,这样做之后原来的图会变成一棵树 or 森林(取决于原图连通与否)。这种把 e-DCC 中的多个节点和边收缩成一个节点的方法,叫做缩点。如下图所示。

e-dcc 的缩点

v-DCC 的缩点:设无向图 $G$ 中有 $p$ 个点双连通分量 $G_{v1}, G_{v2}, …, G_{ep}$,把原来的 $p$ 个 v-DCC 视为独立节点 $i_{1}, i_{2}, …, i_{p}$(如果有点属于多个 v-DCC, 则多个 v-DCC 中都包含该点),在每两个 v-DCC 的公共点部分引入 $t$ 个新节点 $i_{p+1}, i_{p+2}…, i_{p+t} $,这些节点与 v-DCC 间的连边共同构成一棵树。这样称为 v-DCC 的缩点,如下图所示。

v-dcc 的缩点

流图 (Flow Graph)

对有向图 $G = (V, E)$, 若存在点 $r \in V$, 满足从 $r$ 出发,能够到达 $V$ 中的所有点,那么图 $G$ 是一个流图,$r$ 称为流图的源点.

流图中的边 $(x, y)$ 有四种类型:

  1. 树枝边,指 $x$ 为 $y$ 的父节点,这是搜索树中的边;
  2. 前向边,指 $x$ 为 $y$ 的祖先节点;
  3. 后向边,指 $y$ 为 $x$ 的祖先节点;
  4. 横叉边,满足 $dfn[y] < dfn[x]$, 如果一条边不属于上述三种情况之一,那么这条边就是横叉边。

如图所示:

四种流图边类型

强连通分量(有向图)

强连通图:给定一张有向图 $G=(V,E)$, 若对于图中任意两个节点 $x, y$,既存在 $x$ 到 $y$ 的路径,也存在 $y$ 到 $x$ 的路径,则称该图为强连通图

强连通分量 (SCC, strong connected component):有向图的极大强连通子图称为强连通分量。

通俗地讲就是从一张有向图中选出最多 $n$ 个点及其连边构成一张新图,这张新图的每两个点都互相可达。根据定义,环一定是一个强连通图。

有向图的必经点与必经边

有向图的必经点:给定有向图 $G=(V,E)$,起点为 $s$,终点为 $t$,若从 $s$ 到 $t$ 的每条路径都必须经过一个点 $x$,那么 $x$ 就是必经点。
有向图的必经边:若从 $s$ 到 $t$ 的每条路径都经过一条边 $(x,y)$,则 $(x,y)$ 称为必经边或有向图的桥。

这两个定义基本上都是字面意思。

0x02 Tarjan 在无向图中的应用

求割边

首先引入割边(桥)的判定法则:

割边判定法则:如果无向边 $(x, y)$ 是桥,当且仅当 x,y 在搜索树上,y 为 x 的子节点,且 $dfn[x] < low[y]$, 即 x 的 DFS 序小于 y 的追溯值。

证明:根据上面的定义 $low[i]$ 表示由 $i$ 及其子树的节点出发能到达的 $dfn$ 最小的点,如果 $dfn[x] < low[y]$,则说明从点 $y$ 出发,不经过边 $(x, y)$ 无法到达点 $x$ 或比 $x$ 更早访问的节点,此时的图一定分成了两个或以上的部分。

因为搜索树涵盖了每个节点,所以割边(桥)一定是搜索树的边。如果不是的话,那么存在一条不在搜索树上的边 $(x, t)$ 和在搜索树上的边 $(x, y)$ 同时连通两部分,所以割边不可能不在搜索树上。此外,如果有节点相互成环,那么割边也不在环上,因为无论去掉哪条边,环所属的各个点仍然连通。

求出所有的割边,我们可以按照上面的思路,首先计算每个节点的 dfn 和 low 值,然后遍历每个节点 $i$,对于 $i$ 的每条出边 $(i, j)$ 判断,若 $dfn[i] < low[j]$ 则找到了割边。

int cnt = 0;        // dfs 序计数
// tarjan 的主算法,本质是一个 dfs 函数,x 是 dfs 的起点
// in_edge 是入边的编号,如果没有入边则编号 0
void tarjan(int x, int in_edge) {
    dfn[x] = low[x] = ++cnt;        // 初始化
    // 遍历 x 的每条出边
    for (int i = head[x]; i; i = e[i].next) {
        int y = e[i].v;
        if (!dfn[v]) {  // 点 y 未被访问
            tarjan(v, i);
            low[x] = std::min(low[x], low[y]);
            // 割边判定法则
            if (low[y] > dfn[x]) {
                printf("find bridge: %d, %d\n", e[i].u, e[i].v);
            }
        }
        // (in_edge) ^ 1 表示与入边对应的无向边,如果 i 也不是对边对应的无向边那就不在搜索树中
        else if (i != (in_edge ^ 1)) {
            low[x] = std::min(low[x], dfn[y]);
        }
    }
}
// 对每个未访问的点执行主算法
for (int i = 1; i <= n; i++)
    if (!dfn[i])
        tarjan(i, 0);

求割点

割点的判定法则如下,与割边的大同小异:

若 $x$ 是搜索树的根节点,则 $x$ 是割点当且仅当 $x$ 有 2 个或以上的子节点。
若 $x$ 不是搜索树的根节点,则 $x$ 是割点,当且仅当搜索树上存在 $x$ 的一个子节点 $y$, 满足 $dfn[x] \leq low[y]$。

证明:若 $x$ 是根节点,显然删掉 $x$ 后,$x$ 的子树分别成独立的图;若 $x$ 不是根节点且满足上述条件,说明从 $y$ 出发无法到达比 $x$ 更早被访问的节点(但是能访问到 $x$,鉴于 $x$ 会被删除,因此访问了也没有关系)。

求割点仍然是先计算每个节点的 dfn 和 low 值,然后遍历每个节点 $i$,若 $i$ 是根节点则判断 $i$ 的子节点数;若不是则对于 $i$ 的每条出边 $(i, j)$ 判断 $dfn[i] \leq low[j]$ 即可。

int cnt = 0, root = 0;
void tarjan(int x) {
    dfn[x] = low[x] = ++cnt;
    int child_count = 0;
    for (int i = head[x]; i; i = e[i].next) {
        int y = e[i].v;
        if (!dfn[y]) {
            tarjan(y);
            low[x] = std::min(low[x], low[y]);
            if (low[y] >= dfn[x]) {
                child_count++;
                if (x != root || child_count > 1)
                    printf("find cut point %d\n", x);
            }
        } else {
            low[x] = std::min(low[x], dfn[y]);
        }
    }
}

for (int i = 1; i <= n; i++)
    if (!dfn[i])
        root = i, tarjan(i);

求无向图的双连通分量

有关于双连通分量的定义,我们在前面探讨过了。接下来我们分别从求 v-DCC 和求 e-DCC 入手。

求无向图的点双连通分量 v-DCC

首先引入判定一张无向图是否为点双连通图的法则。无向连通图是点双连通图时,当且仅当该图满足以下两个条件之一:

  1. 图的顶点数不超过 2,即 $n \leq 2$;
  2. 图中任意两点同时包含在至少一个简单环(指不自交的环,就是起点终点都是自己的环)中。

例如,在上面的图中,我们有四组点双连通分量,分别是 1,2,3,4,5 / 1,6 / 6,7 / 6,7,8. 在这些点双连通分量中,任选其中一个点出发,一定能够到达分量中的其它任意一点。

v-DCC example

求无向图的点双连通分量,我们需要额外维护一个栈。按照以下的流程来维护栈中的元素:

  1. 循环遍历每一个节点,若发现某个节点的 $dfn[i]$ 未被计算,则以该点为入口执行 Tarjan 算法;
  2. 当一个节点第一次被访问的时候,将该节点入栈;
  3. 遍历节点 $x$ 的每条出边 $(x, y)$,判断 $x$ 是否为割点,即 $dfn[x] \leq low[y]$ 是否成立;
  4. 若 $x$ 为割点,则从栈顶不断弹出节点,直到节点 $y$ 被弹出或栈为空;弹出的所有节点与 $x$ 共同构成一个 v-DCC.

比如说,在上面的图中,容易看出割点为 1, 6. 我们不妨以 1 为起点开始执行 Tarjan,1->2->3->4->5,栈中元素为 5,4,3,2,1;然后回溯到 1 时,发现有 $dfn[1] \leq low[2]$,说明 1 是割点。那么此时弹出栈中的元素直到 2 被弹出为止,弹出 5,4,3,2,最后 1 也是 v-DCC 的一部分,将其加入;然后搜索 6,6 往下搜索 7 / 8,9 又分别得到两个新的 v-DCC;最后回溯到点 1 时,发现 $dfn[1] \leq low[6]$,1-6 构成一个双连通分量。那么直接把 6 取出,与 1 一起得到一个新的 v-DCC. 这样我们就找到了全部的四个 v-DCC.

另外需要额外注意处理一下一个点单独孤立的情况,此时这个点自身形成一个 v-DCC. 最后,汇合起来代码如下:

代码如下:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#include <vector>
const int MAXN = 100000;
struct Edge {
    int u, v, next;	
} e[MAXN << 1];
int head[MAXN], cnt = 1, n, m;
int dfn[MAXN], low[MAXN], dcnt = 0, root = 0;
bool cut[MAXN];      // 记录点 i 是不是割点,这个待会会用到
int ans = 0;
std::stack<int> s;
std::vector<int> dcc[MAXN];
void addEdge(int u, int v) {
    e[cnt] = (Edge) {u, v, head[u]};
    head[u] = cnt;
    cnt++;
}
void tarjan(int x) {
    dfn[x] = low[x] = dcnt++;
    s.push(x);
    if (x == root && head[x] == -1) {		// 孤立点,单独成图 
        dcc[ans++].push_back(x);
        return;
    }
    for (int i = head[x]; i; i = e[i].next) {
        int y = e[i].v;
        if (!dfn[y]) {
            tarjan(y);
            low[x] = std::min(low[x], low[y]);
            if (low[y] >= dfn[x]) {		// x 是割点 
                cut[x] = 1;
                int tmp;
                do {
                    tmp = s.top();
                    s.pop();
                    dcc[ans].push_back(tmp);
                } while (tmp != y);
                dcc[ans].push_back(x);
                ans++;
            }
        } else {
            low[x] = std::min(low[x], dfn[y]);
        }
    }
}
int main() {
    memset(e, -1, sizeof e);
    scanf("%d%d", &n, &m);
    int u, v;
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &u, &v);
        addEdge(u, v);
        addEdge(v, u);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) {
            root = i;
            tarjan(i);
        }
    }
    for (int i = 0; i < ans; i++) {
        printf("v-DCC #%d\n", i);
        for (int j = 0; j < dcc[i].size(); j++)
            printf("%d ", dcc[i][j]);
        printf("\n");
    }
    return 0;
}

测试数据:

9 11
1 2
2 3
3 4
4 5
2 5
1 5
1 6
6 7
6 8
8 9
6 9

求无向图的 e-DCC

求无向图的边双连通分量就比较简单,首先我们使用 Tarjan 算法标记处所有的桥,然后对整个无向图进行一次 DFS,对于节点 $x$ 的出边 $(x, y)$,如果它是割边,则跳过这条边不沿着它往下走;这样我们可以划分出多个连通块,连通块的数目及其包括的节点,就是我们所求的 e-DCC 的数量和包含的节点。

以上面的图为例,图中应该有 2 条割边 (1, 6) 和 (6, 7),因此有 3 个边双连通分量,如图所示:

e-dcc example

我们设置一个新的变量 $c[i]$ 来表示节点 $i$ 所属的 $e-DCC$ 的编号。可以发现,删去割边后,我们在一次 DFS 中访问到的节点都在同一个 e-DCC 中,所以具有相同的 $c[i]$ 值。代码如下:

#include <cstdio>
#include <cstring>
#include <algorithm>
const int MAXN = 100000;
struct Edge {
    int u, v, next;	
} e[MAXN << 1];
int head[MAXN], cnt = 2, n, m;		// 为了进行异或运算找到边,必须设定前向星 cnt 起点为 2 
int dfn[MAXN], low[MAXN], dcnt = 0;
int c[MAXN], dcc = 0;
bool is_bridge[MAXN];
void addEdge(int u, int v) {
    e[cnt] = (Edge) {u, v, head[u]};
    head[u] = cnt;
    cnt++;
}
void tarjan(int x, int in_edge) {
    dfn[x] = low[x] = dcnt++;
    for (int i = head[x]; i; i = e[i].next) {
        int y = e[i].v;
        if (!dfn[y]) {
            tarjan(y, i);
            low[x] = std::min(low[x], low[y]);
            if (low[y] > dfn[x]) {		// x 是割边 
                printf("edge (%d, %d) is bridge.\n", x, y);
                is_bridge[i] = is_bridge[i ^ 1] = 1;	// 标记该边及其反向边为桥 
            }
        } else if (i != (in_edge ^ 1)) {
            low[x] = std::min(low[x], dfn[y]);
        }
    }
}
void dfs(int x) {
    c[x] = dcc;
    for (int i = head[x]; i; i = e[i].next) {
        int y = e[i].v;
        // 节点 y 已被访问或者 (x,y) 是桥 
        if (c[y] || is_bridge[i])
            continue;
        dfs(y);
    }
}
int main() {
    memset(e, -1, sizeof e);
    scanf("%d%d", &n, &m);
    int u, v;
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &u, &v);
        addEdge(u, v);
        addEdge(v, u);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) {
            tarjan(i, 0);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (!c[i]) {
            dcc++;
            dfs(i);
        }
    }
    printf("There are %d e-DCCs.\n", dcc);
    for (int i = 1; i <= n; i++) {
        printf("node %d belongs to e-dcc %d\n" , i, c[i]);
    }
    return 0;
}

e-DCC 的缩点

对无向图的边双连通分量进行缩点很简单,因为我们上面已经求出了每个点所属的 e-DCC, 因此我们只需要遍历每条边 $(x, y)$,如果这条边所连的点 $x, y$ 有 $c[x] = c[y]$,说明他们属于同一个 e-DCC,不需要做任何事情;否则,说明 $(x, y)$ 是割边,将 x, y 加入一张新的图中。完成后新的图就是我们想要的缩完点之后的树或森林。

下面是 e-DCC 缩点的代码,配合上面求 e-DCC 的代码食用。

Edge ec[MAXN << 1];
int hc[MAXN], cecnt = 2;
void add_cut_edge(int u, int v) {
    ec[cecnt] = (Edge) {u, v, hc[u]};
    hc[u] = cecnt++;
}
for (int i = 2; i <= cnt; i++) {    // cnt 是原图的边数
    int x = e[i].x, y = e[i].y;
    if (c[x] == c[y])
        continue;                   // x, y 同属一个 e-DCC, 无事可做
    add_cut_edge(x, y);             // 否则将 x, y 加入新树中
}

printf("finish point reducing operation, new tree/forest has %d nodes and %d edges: \n", dcc, cecnt / 2); // 除 2 是因为有重边
for (int i = 2; i < cecnt; i += 2)
    printf("%d %d\n", e[i].u, e[i].v);

v-DCC 的缩点

v-DCC 的缩点由于引入了新的关联节点,因此就显得比较复杂。在求完 v-DCC 的基础上,我们的操作步骤是这样的:

  1. 给每个割点一个新的编号,从 ans+1 开始,ans 表示 v-DCC 的个数。
  2. 建立一张新的图,加入每个 v-DCC 和该 v-DCC 所包含的所有割点的连边。

大家可以对照着 0x01 的定义部分,模拟一下上面的步骤。下面是代码,熟读并背诵即可

// 给割点编号
int new_id[MAXN], num = ans;
for (int i = 1; i <= n; i++)
    if (cut[i])
        new_id[i] = ++num;

// 建立新图
Edge ec[MAXN << 1];
int hc[MAXN], cdcnt = 2;
void add_vdcc_edge(int u, int v) {
    ec[cdcnt] = (Edge) {u, v, hc[u]};
    hc[u] = cdcnt++;
}
for (int i = 0; i < ans; i++) {          // ans 是 v-DCC 数 -1
    for (int j = 0; j < dcc[i].size(); j++) {
        int x = dcc[i][j];
        if (cut[x]) {
            add_vdcc_edge(i, new_id[x]);
            add_vdcc_edge(new_id[x]. i);
        } else {
            c[x] = i;           // 除了割点之外,标记其它的点只属于一个 v-DCC
        }
    }
}

printf("finish point reducing operation, new tree/forest has %d nodes and %d edges: \n", ans, cdcnt / 2); // 除 2 是因为有重边
for (int i = 2; i < tc; i += 2) {
    printf("%d %d\n", e[i].u, e[i].v);
}

0x03 Tarjan 在有向图中的应用

求有向图的强连通分量

在定义一节中我们提到,一个环一定是一个强连通图。因此,Tarjan 算法求解有向图的强连通分量的基本思路,就是对于每个节点 $i$,尽量找到能与它一起成环的所有节点;找到这些节点之后自然就找到了一张原图的极大连通子图,也就是强连通分量 SCC.

刚刚我们提到,一张流图中有四种边,分别为“树枝边”、“前向边”、“后向边”和“横叉边”。现在我们考虑搜索树上的节点加上这些边如何能成环。根据刚才的定义,后向边是由搜索树中的子节点指向祖先节点的边,因此后向边连通的两个点及两个点在 DFS 中经过的节点一定构成环。而横叉边比较特殊,如果存在一条横叉边 $(x,y)$,满足从 $y$ 出发能找到一条路径回到 $x$ 的祖先节点,那么 $(x, y)$ 就是有用的。

接下来就是,如何利用这两类边去找环。我们需要维护一个栈,当 Tarjan 主算法进行 DFS 到节点 $x$ 的时候,栈中需要保存两类节点:第一类是 $anc(x)$,即 $x$ 在搜索树上的祖先节点的集合;第二类是节点 $i$ 满足 $vis[i] = 1$ 且 $\exists e_{ij}$ 使 $e_{ij}$ 连接 $i$ 和 $anc(x)$ 中的一点(也就是说已访问过、并且存在一条路径到达 $anc(x)$ 集合元素的节点)。我们分别说说存这两类节点有什么意义。

首先是维护 $anc(x)$ 的意义,设 $y$ 是 $x$ 的一个祖先节点即 $y \in anc(x)$, 如果存在后向边 $(x, y)$,则 $y$ 到 $x$ 的路径与边 $(x, y)$ 共同成环。其次是维护已访问过可达 $anc(x)$ 的点的意义,主要用于处理横叉边,如果有节点 $z$ 满足从 $z$ 出发存在一条路径可以到达 $y \in anc(x)$, 那么如果存在横叉边 $(x,z)$,则 $z \to y$, $y \to x$ 和边 $(x, z)$ 成环。

栈的作用图解

同样的,我们在有向图的 Tarjan 中也存在追溯值的概念。基本计算方法和无向图的追溯值方法是大同小异的,因为引入了边的方向,所以我们在 DFS 和回溯计算的时候需要特别注意:

  1. $dfn$ 与 $low$ 的初始化,与无向图中求追溯值相同,令 $dfn[x] = low[x] = ++order$.
  2. 扫描 $x$ 的每条出边 $(x,y)$,如果 $y$ 是搜索树上的节点($(x, y)$ 是树枝边),那么 $y$ 就没有被访问过,计算完 $low[y], dfn[y]$ 回溯时令 $low[x] = min(low[x], low[y])$.
  3. 如果 $y$ 不是搜索树上的节点,那么 $y$ 一定被访问过,此时 $(x, y)$ 是后向边,令 $low[x] = min(low[x], dfn[y])$.
  4. 从 $x$ 回溯之前判断是否有 $low[x] = dfn[x]$ 成立,如果是的话将栈顶元素弹出直到 $x$ 出栈为止

可以发现,有向图的 Tarjan 算法相比无向图,在判断 $(x,y)$ 是否为搜索树上的边时,用的是指向的结点是否在栈中的判断法;并且有向图在计算完 $low[x]$ 之后,还需要根据条件 $low[x] = dfn[x]$ 是否成立,将栈顶元素弹出,防止后面的 DFS 过程中误将其它分支的节点当做祖先节点。

以前文的有向图为例计算追溯值,特别注意圈出来的几个节点:因为节点 $5$ 存在通向祖先节点 $2$ 的节点,所以 $low[5] = dfn[2] = 2$,再层层回溯,得到 $low[2] = low[3] = low[4] = low[5] = 2$. 最后在回溯到 $2$ 的时候,发现 $dfn[2] = low[2]$ 成立,那么弹出栈中的元素 $5,4,3,2$.
$6-8-9$ 的搜索也同理。
注意节点 $7$,虽然它有一条指向 $4$ 的横叉边,但是搜索到 $7$ 的时候,$4$ 已经不在栈中了,说明这条横叉边并没有什么存在的意义。注意我们之前说过,横叉边 $(x, y)$,只有从 $y$ 能找到一条通往 $x$ 及其祖先节点的路径,这条边才有用。

有向图的追溯值计算示意图

说了这么多,我们还没有说到用 Tarjan 到底怎么求有向图的强连通分量。其实很简单,在上面的图中我们发现,四个强连通分量是 2,3,4,5 / 6,8,9 / 7 / 1;而这两个强连通分量都是计算追溯值的第四步中,从栈里弹出来的节点。也就是说我们得到了 Tarjan 算法中强连通分量的判定法则:

在追溯值的计算过程中,若从 $x$ 回溯前,有 $low[x] = dfn[x]$ 即 $x$ 的追溯值=DFS序,那么在栈中,从 $x$到栈顶的所有节点构成一个强连通分量。

注意我在判定法则前加了一个定语“Tarjan 算法中”,说明这个法则只有在 Tarjan 算法的特定场景下有意义。上述法则的合理性在于,如果 $dfn[x] = low[x]$,说明子节点可以到达 $x$, 但并不能到达比 $x$ 更早被 DFS 的节点,自然不会和更先前的点成环。

模板代码如下:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#include <vector>
using std::stack;
using std::vector;
const int MAXN = 100000;
struct Edge {
    int u, v, next;
} e[MAXN << 1];
int head[MAXN], cnt = 1;
int dfn[MAXN], low[MAXN], order = 1;
int c[MAXN];			// 缩点的时候会用到,表示节点 i 所属的 scc 编号 
int n, m, scccnt = 0;
bool instack[MAXN];
vector<int> scc[MAXN];
stack<int> s;
void addEdge(int u, int v) {
    e[cnt] = (Edge){ u, v, head[u] };
    head[u] = cnt++;
}
void tarjan(int x) {
    dfn[x] = low[x] = order++;
    s.push(x);
    instack[x] = 1;
    for (int i = head[x]; i; i = e[i].next) {
        int y = e[i].v;
        if (!dfn[y]) {
            tarjan(y);
            low[x] = std::min(low[x], low[y]);
        } else if (instack[y]) {
            low[x] = std::min(low[x], dfn[y]);
        }
    }
    if (dfn[x] == low[x]) {
        int tmp;
        do {
            tmp = s.top();
            c[tmp] = scccnt;
            instack[tmp] = 0;
            s.pop();
            scc[scccnt].push_back(tmp);
        } while (tmp != x);
        scccnt++;
    }
}
int main() {
    scanf("%d%d", &n, &m);
    int u, v;
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &u, &v);
        addEdge(u, v);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) {
            tarjan(i);
        }
    }
    printf("Find %d SCC(s.\n", scccnt);
    for (int i = 0; i < scccnt; i++) {
        printf("SCC #%d: ", i);
        for (int j = 0; j < scc[i].size(); j++)
            printf("%d ", scc[i][j]);
        printf("\n");
    }
    return 0;
}

测试数据:

9 13
1 2
2 3
3 4
4 5
5 2
1 5
1 6
6 7
7 4
8 7
6 8
8 9
9 6

SCC 的缩点

SCC 的缩点和 e-DCC 的缩点比较类似,不过最后得到的应该是一张 DAG(有向无环图)。上面我们用 $c[i]$ 记录了节点 $i$ 所属的 SCC 的编号,我们对原图的每条边 $(x,y)$ 遍历判断,若 $c[x] \neq c[y]$,就在编号为 $c[x]$ 与 $c[y]$ 的 SCC 之间连边。

Edge ec[MAXN];
int hc[MAXN], ccnt = 1;
void add_scc_edge(int u, int v) {
    ec[ccnt] = (Edge) { u, v, hc[u] };
    hc[u] = ccnt++;
}

for (int x = 1; x <= n; x++) {
    for (int i = head[x]; i; i = e[i].next) {
        int y = e[i].v;
        if (c[x] == c[y])
            continue;
        add_scc_edge(c[x], c[y]);
    }
}

0x04 One More Thing - Kosaraju

到上面为止 Tarjan 算法就讲的差不多了。不知道读者有什么感想,我第一次看这些东西的时候满脑子的 WTF,说好要用简明的语言复述一遍,这样下来我已经混乱了。因为 Tarjan 实在是太复杂了(虽然理解之后,代码量是很小的),这里还是要再讲一种稍微简单些的,用来求有向图的强连通分量的算法——Kosaraju 算法。

Kosaraju 算法也可以在线性时间内求出有向图的强连通分量。虽然 Kosaraju 的时间也是线性的,但是因为 Kosaraju 的算法步骤需要对图进行两次遍历,而 Tarjan 算法只需要遍历一次图中的节点,因此实际运用中 Kosaraju 的效率是要略低于 Tarjan 的,但是 Kosaraju 的原理比 Tarjan 简单的呢。有多简单呢?我们来看一张有向图:

kosaraju-example-1

在上图中,如果不计单点自己组成的强连通分量,那么很明显有两个强连通的子图:1,2,3 / 5,6,7. 现在我们对这张有向图的边取反(就是把原来的边方向反过来),得到图$G_r$:

kosaraju-example-2

此时,我们任选 $G_r$ 中的一个节点为起点,利用深度优先搜索求出 $G_r$ 的逆后序。什么是逆后序呢?我们的 DFS 节点顺序分为前序、后序、逆后序三种,取决于节点在何时被加入什么样的数据结构中,一般我们定义:

前序:在递归调用下一级 DFS 函数之前,将当前节点加入队列
后序:在递归调用下一级 DFS 完成回溯之后,将当前节点加入队列
逆后序:在递归调用下一级 DFS 完成回溯之后,将当前节点加入

因此,以 $5$ 为 DFS 起点对 $G_r$ 求逆后序,入栈顺序是:6 7 1 2 3 4 5,而逆后序是从栈顶到栈底的顺序,则逆后序是 5 4 3 2 1 7 6.

接下来,我们按照得到的逆后序,再对原图进行一次 DFS:在同一个 DFS 递归子程序中访问的点,一定是同属一个连通分量的,例如对上面的图,如下图所解释:

kosaraju-explanation

这样就求出有向图的强连通分量啦。让我们来理一遍主算法的思路:

  1. 对于有向图 $G$, 将其每条边取逆 ($(x, y) \to (y, x)$),得到一张新图 $G_r$,这是 $G$ 的反向图;
  2. 建立一个栈 $s$, 遍历图 $G_r$ 所有的节点,进行 DFS 求逆后序,并标记已访问的节点;
  3. 按照 $s$ 栈顶到栈底的节点顺序,对 $G$ 再进行一次 DFS,同一个 DFS 递归子程序中访问的点同属一个 SCC.

代码如下,我实在很难找到网上有的 Kosaraju 的算法 C++ 版本,所以自己撸了一个:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#include <vector>
using std::stack;
using std::vector;
const int MAXN = 100000;
struct Edge {
	int u, v, next;
} e[MAXN << 1], rev[MAXN << 1];
int head[MAXN], head_rev[MAXN], cnt = 1, scccnt = 0;
int n, m;
bool vis[MAXN];
vector<int> scc[MAXN];
stack<int> reverse_postorder, s2;
void addEdge(int u, int v) {
	e[cnt] = (Edge){ u, v, head[u] };
	head[u] = cnt++;
}
void reverse_graph() {
	for (int i = 1; i < cnt; i++) {
		rev[i] = (Edge){ e[i].v, e[i].u, head_rev[e[i].v] };
		head_rev[e[i].v] = i;
	}
}
void dfs_reverse_postorder(int x) {
	vis[x] = 1;
	for (int i = head_rev[x]; i; i = rev[i].next) {
		if (!vis[rev[i].v]) {
			dfs_reverse_postorder(rev[i].v);
		}
	}
	reverse_postorder.push(x);
}
void dfs(int x, bool root) {
	vis[x] = 1;
	s2.push(x);
	for (int i = head[x]; i; i = e[i].next) {
		if (!vis[e[i].v]) {
			vis[e[i].v] = 1;
			dfs(e[i].v, false);
		}
	}
	if (root && !s2.empty() && s2.size() >= 2) {
		while (!s2.empty()) {
			scc[scccnt].push_back(s2.top());
			s2.pop();
		}
		scccnt++;
	} else if (root) {
		s2.pop();
	}
}
int main() {
	scanf("%d%d", &n, &m);
	int u, v;
	for (int i = 0; i < m; i++) {
		scanf("%d%d", &u, &v);
		addEdge(u, v);
	}
	reverse_graph();
	
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) {
			dfs_reverse_postorder(i);
		}
	}
	
	memset(vis, 0, sizeof vis);
	
	while (!reverse_postorder.empty())  {
		int s = reverse_postorder.top();
		reverse_postorder.pop();
		if (!vis[s])
			dfs(s, 1);
	}
	
	printf("Find %d SCC(s).\n", scccnt);
	for (int i = 0; i < scccnt; i++) {
		printf("SCC #%d: ", i);
		for (int j = 0; j < scc[i].size(); j++) {
			printf("%d ", scc[i][j]);
		}
		printf("\n");
	}
	return 0;
}

0x05 Reference

部分内容和代码参考李煜东的《算法竞赛进阶指南》,在此特别感谢。

©2016-2019  宇宙よりも遠い場所 / Published with Hugo / CC-BY-SA 4.0 Licensed