Tarjan 求有向图的强连通分量

重温Tarjan, 网上看了许多博客感觉都讲的不清楚. 故传上来自己的笔记, 希望帮到大家.

提到的一些概念可以参考 oi wiki, 代码也是 oi wiki 的, 因为我不认为我能写出比大佬更好的代码了.

---

强连通分量: 有向图的最大强连通子图 ( 有向图中任意两点可达 )

• Tarjan

  1. 对每个结点维护:

     • dfn[x]: 当前节点的 dfs 序.

     • low[x]: x 向下搜索能到达的最小 dfs 序.

  2. 更新 low:

     1. v 未被访问过: 初始 low[v] = dfn[v].v 入栈. 回溯时用 low[v] 更新它的 fa 的 low[ ].

     2. v 被访问过, 且还在栈中: 用 dfs[v] 更新 fa 的 low.

     3. v 被访问过, 不在栈中: 说明这是一个 fa 到 v 的单向访问, 跳过.

  3. 获取答案:

     能让 dfn[x] > low[x], 只有当 X 的子树中某个节点 C 有$\{\begin{array}{l}1.\mathrm{一}\mathrm{条}\mathrm{横}\mathrm{向}\mathrm{边}\mathrm{连}\mathrm{接}\mathrm{到}\mathrm{一}\mathrm{棵}\mathrm{已}\mathrm{遍}\mathrm{历}\mathrm{过}\mathrm{的}\mathrm{子}\mathrm{树}A\\ 2.\mathrm{一}\mathrm{条}\mathrm{返}\mathrm{祖}\mathrm{边}\mathrm{连}\mathrm{接}\mathrm{到}X\mathrm{的}\mathrm{祖}\mathrm{先}xfa\end{array}$ .

     1. 横向边: 说明 A 没有连接到 C 的边, 否则在之前 C 就被遍历了, 轮不到 X 来遍历. 就用是否 C 在栈中来排除这个情况, 子树 A 中的所有强连通分量之前已经出栈过了( 看代码的实现 ).
     2. 返祖边: 说明 xfa -> x -> c -> xfa 形成环, 在同一个强连通子图( 我们知道, 强连通图是许多环嵌套成的 ). 而且这个子图的根是 xfa 满足 dfn[xfa] = low[xfa].

     此时栈中进来过三类节点 :

     $$\{\begin{array}{l}1.\mathrm{在}x\mathrm{的}\mathrm{子}\mathrm{树}\mathrm{中}\{\begin{array}{l}1.\mathrm{属}\mathrm{于}\mathrm{上}\mathrm{述}xfa\mathrm{循}\mathrm{环}\mathrm{的},\mathrm{在}\mathrm{同}\mathrm{一}\mathrm{个}\mathrm{强}\mathrm{连}\mathrm{通}\mathrm{子}\mathrm{图}.\\ 2.\mathrm{不}\mathrm{在}\mathrm{同}\mathrm{一}\mathrm{个}\mathrm{强}\mathrm{连}\mathrm{通}\mathrm{子}\mathrm{图},\mathrm{那}\mathrm{递}\mathrm{归}\mathrm{的}\mathrm{讲},\mathrm{在}\mathrm{之}\mathrm{前}\mathrm{就}\mathrm{因}\mathrm{为}\mathrm{属}\mathrm{于}\mathrm{某}\mathrm{个}xf{a}^{\prime }(\mathrm{在}X\mathrm{的}\mathrm{子}\mathrm{树}\mathrm{中}),\mathrm{而}\mathrm{被}\mathrm{踢}\mathrm{出}\mathrm{栈}\mathrm{了}.\end{array}\\ 2.\mathrm{不}\mathrm{在}x\mathrm{的}\mathrm{子}\mathrm{树}\mathrm{中}(\mathrm{即}\mathrm{在}\mathrm{已}\mathrm{遍}\mathrm{历}\mathrm{过}\mathrm{的}\mathrm{子}\mathrm{树}\mathrm{中}),\mathrm{在}\mathrm{栈}\mathrm{中}\mathrm{的}\mathrm{位}\mathrm{置}\mathrm{一}\mathrm{定}\mathrm{在}x\mathrm{的}\mathrm{下}\mathrm{面}.\end{array}$$

     故, 回溯时若节点符合 dfn[x] = low[x], 说明当前节点是它所属连通块的最小节点. 栈里它之上所有点都是一个强连通块.

代码:

 const int Maxn = 1e5 + 10;
    
    int dfn[Maxn], low[Maxn], dfncnt, s[Maxn], in_stack[Maxn], tp;
    int scc[Maxn], sc;  // 结点 i 所在 SCC 的编号
    int sz[Maxn];       // 强连通 i 的大小
    
    void tarjan(int u) {
        low[u] = dfn[u] = ++dfncnt, s[++tp] = u, in_stack[u] = 1;
        for (int i = head[u]; i; i = eg[i].nex) {
            const int &v = eg[i].to;
            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;
        }
    }