深入理解Tarjan算法及其实现

重温Tarjan算法，发现网上的博客大多解释不够清晰。因此，我将分享自己的笔记，希望能帮助到大家。

在讨论的一些概念方面，可以参考oi wiki，代码也来自oi wiki，因为我认为我写不出比专业人士更好的代码。

---

强连通分量： 指有向图中的最大强连通子图（即有向图中的任意两个节点都可以互相到达）。

• Tarjan算法：

  1. 对每个节点维护：

     • dfn[x] ：当前节点的深度优先搜索序号。

     • low[x] ：从节点x向下搜索能到达的最小深度优先搜索序号。

  2. 更新low：

     1. v未被访问过： 初始 low[v] = dfn[v] ，将v入栈。在回溯时，使用low[v]更新其父节点的low[]。

     2. v被访问过，且仍在栈中： 使用dfs[v]更新父节点的low。

     3. v被访问过，但不在栈中： 说明这是一个从父节点到v的单向访问，跳过。

  3. 获取答案：

     当 dfn[x] > low[x] 时，只有当X的子树中某个节点C满足以下条件时：

     1. 横向边：表示A没有连接到C的边，否则C就会在之前被遍历，轮不到X来遍历。可以通过C是否在栈中来排除这种情况，A中的所有强连通分量之前已经出栈过了（参考代码实现）。
     2. 返祖边：表示xfa -> x -> c -> xfa形成环，位于同一个强连通子图中（我们知道，强连通图是由多个嵌套的环组成的）。而且这个子图的根是xfa，并且满足 dfn[xfa] = low[xfa] 。

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

     因此，如果在回溯时节点满足 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;
        }
    }

标签：游戏攻略