tarjan算法

· · 个人记录

①所需要：

（1）low数组，dfn数组

——low[u]记录以u为根的子树中，不算u这个节点最高能跳到哪个节点

——dfn[u]记录u这个节点的编号

（2）存储方式（这里有两种）

——邻接表，即vector，显而易见

——链式前向星，比vector更省空间和时间

②tarjan主体(以这个节点为u为例)

（1）遍历子节点

（2）如果这个子节点没有被遍历过，tarjan(子节点)遍历,然后更新low[u]，即low[u]=min(low[u],low[子节点])

（3）如果已经遍历过了，那也更新low[u]，即low[u]=min(low[u],dfn[子节点])

③在进行tarjan操作时，可进行一些不影响tarjan遍历的操作，如用stack栈等等

④Code代码时间


void tarjan(int u){
    dfn[u]=low[u]=++cnt;
    bj[u]=1;
    for(int i=0;i<v[u].size();i++){
        int g=v[u][i];
        if(!dfn[g]){
            tarjan(g);
            low[u]=min(low[u],low[g]);
        }
        else if(bj[g])
            low[u]=min(low[u],dfn[g]);
    }
}