Tarjan 强连通分量学习笔记

在一个有向图中，如果某两点间都有互相到达的路径，那么称中两个点强连通，如果任意两点都强连通，那么称这个图为强连通图；一个有向图的极大强连通子图称为强连通分量。

Tarjan 算法可以在的时间内求出一个图的所有强连通分量。

定义

Tarjan 算法的核心过程是一次 DFS，它基于的事实是，一个强连通分量中的点一定处于搜索树中同一棵子树中。

栈，搜索树中同一棵子树中的点在栈中是相邻的。

表示进入节点时的时间。

表示由节点开始搜索所能到达的点中，在搜索树上是的祖先且最小的节点的。

算法描述

从起点开始 DFS；
进入一个节点时，初始化它的和均为当前时间戳，并进栈；
枚举当前点的所有邻接点；
如果某个邻接点已在栈中，则更新；
如果某个邻接点未被访问过，则对进行 DFS，并在回溯后更新；
所有邻接点回溯完成后，如果当前点仍满足，则将栈中从到栈顶的所有元素出栈，并标记为一个强连通分量。

解释

枚举的邻接点时，如果某个邻接点已在栈中，则更新

因为栈中的所有点均为搜索树上点的祖先，从搜索树上一个点搜到它的祖先，说明找到了一个环。此时用去更新的最远祖先。

如果某个邻接点未被访问过，则对进行 DFS，并在回溯后更新

点出发能到达的点，点必定也能到达。尽管可能不是的祖先（可能是或本身），但这并不影响。

所有邻接点回溯完成后，如果当前点仍满足

说明从当前点出发不可能回到任意一个搜索树上的祖先，即当前节点是某个强连通分量所在子树的根节点，而这些节点都在当前节点之后被压在了栈中。

注意，同一个强连通分量的点一定有相同的值，值相同的两个点也一定在同一个强连通分量中。

模板

实际代码中要用到两个栈，一个用于控制 DFS（代码中的 s），另一个用于 Tarjan 算法（代码中的 t）。

因为图不一定是弱连通图，所以要以每个点为起点进行一次上述算法。

struct Node {
    Edge *firstEdge, *currentEdge, *inEdge;
    Connected *connected;
    int dfn, low;
    bool inStack, visited, pushed;
} nodes[MAXN];

struct Edge {
    Node *from, *to;
    Edge *next;

    Edge(Node *from, Node *to) : from(from), to(to), next(from->firstEdge) {}
};

struct Connected {
    int size;
} connecteds[MAXN];

int n;

inline int tarjan() {
    int timeStamp = 0, count = 0;

    for (int i = 0; i < n; i++) {
        if (nodes[i].visited) continue;

        std::stack<Node *> s, t;
        s.push(&nodes[i]);
        nodes[i].pushed = true;

        while (!s.empty()) {
            Node *v = s.top();

            if (!v->visited) {
                v->visited = true;
                v->currentEdge = v->firstEdge;
                v->dfn = v->low = timeStamp++;
                v->inStack = true;
                t.push(v);
            }

            if (v->currentEdge) {
                Edge *&e = v->currentEdge;
                if (!e->to->pushed) s.push(e->to), e->to->pushed = true, e->to->inEdge = e;
                else if (e->to->inStack) v->low = std::min(v->low, e->to->dfn);
                e = e->next;
            } else {
                if (v->dfn == v->low) {
                    v->connected = &connecteds[count++];
                    Node *u;
                    do {
                        u = t.top();
                        t.pop();
                        u->inStack = false;
                        u->connected = v->connected;
                        u->connected->size++;
                    } while (u != v);
                }

                if (v->inEdge) v->inEdge->from->low = std::min(v->inEdge->from->low, v->low);

                s.pop();
            }
        }
    }

    return count;
}