Tarjan 详解

· · 算法·理论

tmd，前两天 cls 讲 SCC, 只讲了 Kosaraju，这是对 Tarjan 算法的极大的不尊重。

Robert E. Tarjan（罗伯特·塔扬，1948~），生于美国加州波莫纳，计算机科学家。

Tarjan 发明了很多算法和数据结构。不少他发明的算法都以他的名字命名，以至于有时会让人混淆几种不同的算法。比如求各种连通分量的 Tarjan 算法，求 LCA（Lowest Common Ancestor，最近公共祖先）的 Tarjan 算法。并查集、Splay、Toptree 也是 Tarjan 发明的。

我们这里要介绍的是在有向图中求连通分量的 Tarjan 算法。 —— OI-Wiki.org

首先，我们知道，对图进行 \text{\large D\small epth\large F\small irst\large S\small earch}，可以生成一棵树。

其中，有四种边：

结论 1：对于任意的 u，若 u 是其所在强连通分量的第一个访问的节点，那么以 u 为根的子树一定包含了该强连通分量。

反证法：设 v 在 u 所在强连通分量，以 u 为根的子树不包含 v。那么 v 必然在 u 之前访问过，不然 v 就处于 u 的子树中。此时与 u 是其所在强连通分量的第一个访问的节点矛盾。

现在我们来讲 Tarjan 求强连通分量的过程。

首先，我们有一个栈。

定义 dfn_i 为 i 的 DFS 序， low_i 为以 i 为根的子树中横叉边或返祖边连接的 dfn 最小的在栈中节点的 dfn。

我们按照 Dfs 对图进行以下操作： 维护每个结点的 dfn 与 low，且让搜索到的结点入栈。每当找到一个强连通元素，就按照该元素包含结点数目让栈中元素出栈。对于每一个搜索到的 u，若存在单项边 u\to v，考虑三种情况：

在回溯的过程中，判定 low_u = dfn_u 是否成立，如果成立，则栈中 u 及其上方的结点构成一个 SCC。因为此时必然有边从子树到 u。

代码：

//摘自 OI-wiki
int dfn[N], low[N], dfncnt, s[N], in_stack[N], tp;
int scc[N], sc;  // 结点 i 所在 SCC 的编号
int sz[N];       // 强连通 i 的大小

void tarjan(int u) {
  low[u] = dfn[u] = ++dfncnt, s[++tp] = u, in_stack[u] = 1;
  for (int i = h[u]; i; i = e[i].nex) {
    const int &v = e[i].t;
    if (!dfn[v]) {
      tarjan(v);
      low[u] = min(low[u], low[v]);
    } else if (in_stack[v]) {
      low[u] = min(low[u], dfn[v]);
    }
  }
  if (dfn[u] == low[u]) {
    ++sc;
    while (s[tp] != u) {
      scc[s[tp]] = sc;
      sz[sc]++;
      in_stack[s[tp]] = 0;
      --tp;
    }
    scc[s[tp]] = sc;
    sz[sc]++;
    in_stack[s[tp]] = 0;
    --tp;
  }
}

时间复杂度 O(n+m)。实际上，由于只需要一次 Dfs 且 常数小，因此 Tarjan 算法的效率由于 Kosaraju 算法。

啊？Lca？不能写树剖吗？

Tarjan 求边双连通分量

我相信你知道这是什么意思。

首先，由于是无向图，所以没有横叉边。

搜索树上构成环当且仅当出现返祖边，即在无向图中该分量内不会出现桥，容易发现的是搜索树最终可以被划分为类似环-桥-环的结构，与边双联通分量的定义实际上是相符的。

因此，对于每一个 u，扩展到的 v 只有两种情况：子树与返祖/前向边，此时找到的强连通分量就是双联通分量。

void tarjan(int u, int f) {//f 记录从哪条边来，处理重边
    low[u] = dfn[u] = ++idx;
    st.push(u);
    for(auto [v, x] : g[u])
        if(x != f)
        if(!dfn[v])tarjan(v, x), low[u] = min(low[u], low[v]);
        else low[u] = min(low[u], dfn[v]);
    if(low[u] == dfn[u]) {
        ++ top;
        while(1) {
            int v = st.top();
            st.pop();
            dcc[v] = top;
            sz[top] ++;
            ans[top].push_back(v);
            if(v == u)break;
        }
    }
}

点双以后再写。