图论入门：Tarjan算法及其应用

简介

Tarjan算法由罗伯特·塔杨发明，是一个基于DFS的线性时间复杂度算法，主要用于求解有向图的强连通分量和无向图的割点与桥。

在这里我们继续统一使用祖传邻接表（链式前向星）存储图，邻接表的定义如下：

constexpr int maxn = 100000 + 5;

int head[maxn], cnt = 0;
struct Edge {
    int v, next;
} edges[maxn * 2];

void add_edge(int u, int v) {
    edges[cnt].v = v;
    edges[cnt].next = head[u];
    head[u] = cnt++;
}

基本原理

从任意一个节点出发，构造它的一棵DFS树，并且记录下访问的时间戳dfn数组，同时用low数组表示能够构成闭合回路的DFS树的结点中时间戳的最小值，最后通过low的值和dfn的值判断所需要求解的答案。

应用一：有向图的强连通分量

有向图强连通分量：在有向图$ G $中，如果两个顶点$ v_i $, $ v_j $间（$ v_i $ > $ v_j $）有一条从$ v_i $到$ v_j $的有向路径，同时还有一条从$ v_j $到$ v_i $的有向路径，则称两个顶点强连通。如果有向图$ G $的每两个顶点都强连通，称$ G $是一个强连通图。有向图的极大强连通子图，称为强连通分量。
强连通分量是Tarjan算法最经典的应用，详细解释写在注释中。

void tarjan(int u) {
    dfn[u] = low[u] = time++;
    stack[++top] = u;                 // 所有在同一棵DFS树中的结点全部入栈
    inStack[u] = true;
    for (int e = head[u]; e; e = edges[e].next) {
        int v = edges[e].v;
        if (!dfn[v]) {                // 用时间戳代表是否访问过
            tarjan(v);
            low[u] = min(low[u], low[v]);    // 在同一DFS树中，low值全部相同
        }
        else if (inStack[v])          // 找到了DFS树中的回路
            low[u] = min(low[u], dfn[v]);     // 此处用low[v]代替dfn[v]无妨，但下面的代码不行
                                              // 割点两边可以组成强连通分量，但去掉割点后就不行了
                                              // 所以用dfn而不是low区分开割点的两侧
    }    
    if (dfn[u] == low[u]) {           // u是DFS树的根节点，把整棵树出栈
        int cur;
        do {
            cur = stack[top--];
            inStack[cur] = false;
        } while(cur != u);
    }
}

应用二：无向图的割点与桥

割点：若从图中删除节点 x 以及所有与 x 关联的边之后，图将被分成两个或两个以上的不相连的子图，那么称 x 为图的割点。
桥：若从图中删除边 e 之后，图将分裂成两个不相连的子图，那么称 e 为图的桥或割边。

在无向图加边时，我们一次加两条相互反向的边，假设其中一条编号为$ e $，则可以证明其反向边编号就为$ e ^ 1 $。（编号从0开始）

代码一：桥

bool bridge[maxn * 2];

void tarjan(int u, int eu) {                    // eu表示来时的路
    dfn[u] = low[u] = time++;
    for (int e = head[u]; e; e = edges[e].next) {
        int v = edges[e].v;
        if (!dfn[v]) {
            tarjan(v, e);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u])                 // 如果不沿着来的路回去，那么两边被断开，low没有被较早的dfn更新
                bridge[e] = bridge[e ^ 1] = true; // 也就是说这条边就是桥
        }
        else if (e != eu ^ 1)                   // 这条边不是来时的路的反向边
            low[u] = min(low[u], dfn[v]);
    }
}

代码二：割点

bool cut[maxn];

void tarjan(int u, int eu, int root) {          // root存储了DFS树的根节点
    dfn[u] = low[u] = time++;
    int children = 0;                           // 记录下以u为根的子树个数
    for (int e = head[u]; e; e = edges[e].next) {
        int v = edges[e].v;
        if (!dfn[v]) {
            children++;
            tarjan(v, e);
            low[u] = min(low[u], low[v]);
            if (u != root && low[v] >= dfn[u])   // 割点的两侧一边带等号，一边不带等号
                cut[u] = true;
        }
        else if (e != eu ^ 1)
            low[u] = min(low[u], dfn[v]);
    }
    if (children >= 2 && u == root)              // 拥有两棵DFS树的根节点一定是割点
        cut[u] = true;
}