tarjan 速成

如题，这是一个只适合快速了解的文章，如果要学习 tarjan 那么请阅读其他文章。

用 \(Sub(i)\) 表示 \(i\) 的子树，那么 \(low_i\) 表示 \(Sub(i)\) 中的节点和 \(Sub(i)\) 中的节点经过一条非树边可以到大的节点中 \(dfn\) 的最小值，用 \(dfn_i\) 表示 \(i\) 的时间。

从随便一个节点开始向下跑 dfs，假设现在访问到了 \(x\)，那么 \(dfn_x\).

访问所有的儿子，如果儿子没有访问过那么儿子进行递归操作，接着用儿子的 \(low\) 更新 \(low_x\)。

如果访问过了这个儿子，那么用儿子的 \(dfn\) 更新 \(low_x\)。

强连通分量

对于强连通分量，每一次更新 \(dfn\) 时把 \(x\) 加入栈中。

在所有操作结束之后，如果 \(low_x=dfn_x\) 那么一直访问栈内元素直到访问到 \(x\) 结束操作。

访问到的所有的点构成了一个强连通分量，需要注意没有弹出操作。

割点

talk 没有直接给代码来的快。

void dfs(int x){
    low[x]=dfn[x]=++tot;
    int son=0;
    for(int i:v[x]){
        if(!dfn[i]){
            son++,dfs(i);
            low[x]=min(low[x],low[i]);
            if(low[i]>=dfn[x]&&x!=rt) s.insert(x);
        }
        else{
            low[x]=min(low[x],dfn[i]);
        }
    }
    if(son>=2&&x==rt) s.insert(x);
}

割边

把 \(low_i\ge dfn_x\) 改成 \(low_i\gt dfn_x\) 就行了，而且不用判断根节点的情况。