Tarjan 强连通分量学习笔记

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

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

定义

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

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

表示进入节点 时的时间。

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

算法描述

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

解释

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

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

如果某个邻接点 未被访问过,则对 进行 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;
}