Tarjan算法 解决LCA(最近公共子祖先)问题

推荐blog: https://www.cnblogs.com/jvxie/p/4854719.html

有手动编译的流程, 有助于理解算法

伪代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
tarjan(u) {
    DFN[u]=Low[u]=++Index                      // 为节点u设定次序编号和Low初值
    Stack.push(u)                              // 将节点u压入栈中
    for each (u, v) in E                       // 枚举每一条边
        if (v is not visted)               // 如果节点v未被访问过
            tarjan(v)                  // 继续向下找
            Low[u] = min(Low[u], Low[v])
        else if (v in S)                   // 如果节点v还在栈内
            Low[u] = min(Low[u], DFN[v])
    if (DFN[u] == Low[u])                      // 如果节点u是强连通分量的根
        repeat
            v = S.pop                  // 将v退栈，为该强连通分量中一个顶点
            print v
        until (u== v)
}

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void tarjan(int u){
    dfn[u]=++cnt;
    low[u]=cnt;
    ins[u]=1;
    s[++top]=u;
    for(register int i=head[u];i;i=nxt[i]){
        int v=vv[i];
        if(dfn[v]==0){
            tarjan(v);
            low[u]=MIN(low[u],low[v]);
        }else if(ins[v])
            low[u]=MIN(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        ins[u]=0;
        while(s[top]!=u){
            //do something
            ins[s[top]]=0;
            top--;
        }
        top--;
    }
}

// by Santiego :

Tarjan 算法总结: https://www.cnblogs.com/santiego/p/9556474.html#强连通分量缩点