Tarjan

简述

Tarjan 用于寻找强连通分量。其遍历所有节点，并在过程中为每一个 节点 标记 访问顺序（唯一标识符） 和 最早可溯源点。初始化时，每一个点的访问顺序和和最早可溯源点是一样的。在遍历过程中，Tarjan 不断地在 DFS 链中更新每个点的最早可溯源点。当遍历所有点后，Tarjan 开始回溯。他总是从 最远的点 开始回溯，并在回溯的过程也同时更新 最早可溯源点，意为 从此点出发，可以找到的最早经过的那个节点。完成后，最早可溯源点 一致的点，应在一个强连通分量中。而 访问顺序 和 最早可溯源点 一致的点则是一个强连通分量的顶点。

我们可以抽象地理解为 Tarjan 有两个阶段。首先，他向前遍历所有节点，构成一个向前的有向图。然后向后回溯遍历所有节点，构成一个向后的有向图。随后将此二张图重叠，将所有完美重叠的部分染色，同样颜色的节点即在一强连通分量中。

详情

前置

在此篇文章开始前，您需要了解这些术语的含义：

什么是 Tarjan

思想模型

Tarjan 算法遍历整张图，将遍历过程记录在栈中，实际上是建立了一个树模型。不过该模型额外具有两种边：返祖边和横叉边。考虑如下图：

                 1 
              /  |   \
            2    |     3
          / | \ /     //  \
         4  |  5    6 --- 7
            | /  \
            8     9

其中，8 -> 2 有边，此边称之为返祖边。而 6 -> 7 有边，此边称之为横叉边。由于这两种边的存在，使某些节点可以返回到他们的祖先处，形成一个环。为了描述这种结构，我们使用这样的数据记录他们：

如果有点 node，且 dfn[node] == earliest_dfn[node] 表示该点是一个可构成强连通分量子树的顶点。因为如果有任何一条边使得它可以回到他的祖先，则他的 earliest_dfn[node] 一定小于 dfn[node]。此时其与其出边可访问到的所有的最早可溯源点为自己的点构成强连通分量。

开始

Tarjan 算法的签名是这样的

void tarjan(int node) 

由于一张图中可能存在多个强连通分量，而 Tarjan 可能无法一次全部找到，我们需要遍历图中所有节点，对于每一个未访问的节点调用 Tarjan。

for (int i = 1; i <= node; i++) {
        if (!dfn[i]) {
            tarjan(i);
        }
    }

根据强连通的定义：在有向图中，若任意两点间有路径可以到达，则该图为强连通图，可以发现，环是强连通分量。利用这一性质，进行 DFS 遍历：

因此，在遍历中，需要这两个数据：

还需要两个很简单的数据，用于生成强连通分量：

搜索、生成

Tarjan 算法是对于整个图而言的，所以即使 Tarjan 会递归或调用多次，但是对于每一个点的访问顺序仍是全局计数的。这是为了保证每一个节点的 dfn 是唯一且有序的，从而使得点之间的比较成为可能。

int dfn_timer = 0;

对于每一个节点 node，将其压入栈并标记，并进行初始化。

dfn[from] = earliest_dfn[from] = dfn_timer++;
myStack.push(from);
inStack[from] = true;

然后，遍历他的所有邻接节点。对于其邻接节点 neighbor，分两种情况讨论

1. 未被访问过

if(!dfn[neighbor]) 即该邻接节点未被访问过。此时，Tarjan 并不知道这个点是当前强连通分量的子节点，还是一个新强连通分量的顶点，所以对其递归调用 tarjan(neighbor)。如果他不再有邻接节点，或者他的所有邻接节点都无法找到一个更早的 最早可溯源点，那么他将自成一个强连通分量。但是，我们也尝试更新他的最早可溯源点。如果他的邻接节点中有路径可以使得当前节点找到更早的最早可溯源点，就会将当前节点纳入那个 最早可溯源点 的强连通分量中。

if (!dfn[to]) {
    tarjan(to);
    // 更新当前节点的 earliest_dfn 为最小的可到达 dfn
    earliest_dfn[from] = min(earliest_dfn[from], earliest_dfn[to]);
}

2. 被访问过

else if (in_stack[neighbor]) 即该邻接节点已经被访问过，这是当前 DFS 链上第二次访问到他。说明我们找到了一个回环，即当前 DFS 链。任何一个有向环本身一定是一个强连通分量，那么我们只需要统一这个环的最早可溯源点即可了。

else if (inStack[to]) {
    // 如果邻接节点在栈中，更新 earliest_dfn
    earliest_dfn[from] = min(earliest_dfn[from], earliest_dfn[to]);
}

当遍历了当前节点的所有邻接节点后，Tarjan 检查他自己是不是一个强连通分量的顶点。如果是，生成这个强连通分量。如果不是，则这个点的 tarjan 结束，其携带着数据回到递归调用的位置参与另一个强连通分量的搜索与生成。

if (dfn[from] == earliest_dfn[from]) {
    ssc_count++;
    int to;
    // 弹出栈中元素，形成一个强连通分量
    do {
        to = myStack.top();
        myStack.pop();
        inStack[to] = false;
        ssc_id[to] = ssc_count;  // 将节点标记为属于当前强连通分量
    } while (to != from);  // 直到回到根节点
}

在「思想模型」文章段中我们已经知道，对于点 node，如果有 dfn[node] == earliest_dfn(node)，则他自身是一个强连通分量的顶点。Tarjan 开始从栈中弹出从当前节点开始进行的 DFS 路径上的所有节点。由于栈具有先入后出的性质，可以直接从栈顶逐个弹出。直到遇到在当前 DFS 路径上最早进入的 当前节点 为止。弹出的节点必定都是属于当前节点作为顶点的强连通分量的，相当于 "摘" 出了一个强连通分量。累计强连通分量编号计数器，将这些节点标记为属于当前强连通分量。

结束

Tarjan 将图修改成我们想要的样子，以便于编写后续的代码和算法。在 Tarjan 结束后，可以使用 ssc_id[] 数组查看所有强连通分量，也可以加以缩点。

时空复杂度

使用

以下，Tarjan 模板代码：

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

 const int MAXN = 10010;  // 最大节点数
 const int MAXM = 100010; // 最大边数

 int node, edge;  // 节点和边的数量
 int node_weight[MAXN];  // 每个节点的权重
 vector<int> graph[MAXN];  // 原图的邻接表
 int dfn[MAXN], earliest_dfn[MAXN], ssc_id[MAXN];  // Tarjan 算法使用的数组
 bool inStack[MAXN];  // 标记节点是否在栈中
 int dfn_timer, ssc_count;  // 时间记录器和强连通分量计数器
 stack<int> myStack;  // Tarjan 算法使用的栈

 // Tarjan 算法寻找强连通分量
void tarjan(int from) {
    // 初始化访问次序和能够追溯的最早节点
    dfn[from] = earliest_dfn[from] = dfn_timer++;
    // 将当前节点压入栈中，并标记为在栈中
    myStack.push(from);
    inStack[from] = true;

    // 遍历所有邻接节点
    for (int to : graph[from]) {
        // 如果邻接节点尚未被访问，递归调用 Tarjan
        if (!dfn[to]) {
            tarjan(to);
            // 更新当前节点的 earliest_dfn 为最小的可到达 dfn
            earliest_dfn[from] = min(earliest_dfn[from], earliest_dfn[to]);
        } else if (inStack[to]) {
            // 如果邻接节点在栈中，更新 earliest_dfn
            earliest_dfn[from] = min(earliest_dfn[from], earliest_dfn[to]);
        }
    }

    // 如果当前节点是一个强连通分量的根节点
    if (dfn[from] == earliest_dfn[from]) {
        ssc_count++;
        int to;
        // 弹出栈中元素，形成一个强连通分量
        do {
            to = myStack.top();
            myStack.pop();
            inStack[to] = false;
            ssc_id[to] = ssc_count;  // 将节点标记为属于当前强连通分量
        } while (to != from);  // 直到回到根节点
    }
}

int main() {
    cin >> node >> edge;

    // 输入每个节点的权重
    for (int i = 1; i <= node; i++) {
        cin >> node_weight[i];
    }

    // 输入图的边
    for (int i = 0; i < edge; i++) {
        int from, to;
        cin >> from >> to;
        graph[from].push_back(to);
    }

    // 执行 Tarjan 算法，找到所有的强连通分量
    for (int i = 1; i <= node; i++) {
        if (!dfn[i]) {
            tarjan(i);
        }
    }

}