我向来玩不明白 Tarjan，每年复习都要理解半天，再写半天，再调半天。

每年都会看到一些野鸡博客，搞得我迷惑半天，今年也是，最终还得感谢 @_Guoyh_ 帮我搞明白了。

为了避免之后继续迷惑，我打算把我迷惑的点记下来。

注意：本博客是作者自己的理解，可能也是野鸡博客，如有错误，还请指出。

代码第6行的含义

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

inline void tj(int p){
    dfn[p]=low[p]=++dfsc;
    st.push(p),instk[p]=1;
    for(int nx:e[p]){
        if(!dfn[nx])tj(nx),low[p]=min(low[p],low[nx]);
        else if(instk[nx])low[p]=min(low[p],dfn[nx]);//第6行
    }
    //第8行
    if(dfn[p]==low[p]){
        int x;++colc;
        do{
            x=st.top();st.pop();
            col[x]=colc;
            instk[x]=0;//第14行
            tot[colc]+=arr[x];
        }while(x!=p);
    }
}

一些博客说（其他的大多数博客都没说），这句是在判断：如果这是一条返祖边，就用终点的 dfn 来更新当前点的 low。

于是我就非常迷惑，如果 instack 是用来判断某一点是否在当前点的祖先??，那么为什么要在弹栈时（14行）清零，而不是在搜完一颗子树时（第8行）清零？

实际上，我们发现博客中的那句话是不对的。

考虑这样一张图：

显然，整个图是一个强连通分量。但是如果按博客的说法，那么因为 2 号点并不是 3 号点的祖先，所以 3->2 这条边不是返祖边，于是 3 号点的 low 无法更新，最终缩出来3号点自己竟然成了一个强连通分量。

我的理解

要理解为什么是判某点是否在栈里头，首先要理解栈的含义：

• 栈里放的是当前搜索过的，所有没有缩掉的点，这意味着他们都是可能与 p 在同一个强连通分量的节点。
• 更确切的说，栈里头的点是当前搜索过的，所有与 p 或者 p 的祖先在同一个强连通分量的点。
• 更确切的说，栈里头的点是当前搜索过的，所有能到 p 的点。

而这句话

1

if(instk[nx])low[p]=min(low[p],low[nx]);

则是看，如果 p 的子树，能跑到这些节点中，dfn 比自己小的节点（但是这个节点不一定是 p 的祖先），那么这个强连通分量就不应该在 p 这里统计（每个强连通分量在该分量中 dfn 最小的节点那里统计，并且可以证明这个节点是强连通分量所有节点的共同祖先）。

举一个野鸡题解的例子：

• Menci的Tarjan博客 其实这个博客上的其他东西还挺不错，尤其是线性基的

判断条件

• 强连通：dfn[p]==low[p]，弹到 p。
• 点双：low[nx]==dfn[p]，则如果 p 不是搜索树的根，或者 p 在搜索树上有多个儿子，p 为割点，弹栈直到 nx（nx 要保留，因为割点可能在多个点双中）
• 边双：dfn[p]==low[p]，弹到 p，当前边为桥。