Tarjan算法

【Tarjan算法】基于对图DFS的算法，每个强连通分量为搜索树中的一棵子树

【辅助数据结构】

1. DFN[u]：为节点u搜索的次序编号(时间戳)
2. Low[u]：u或u的子树能够追溯到的最早栈中结点的次序号

Low(u)=Min {
    DFN(u),
    Low(v), (u,v)为树枝边，u为v的父节点
    DFN(v), (u,v)为指向栈中节点的后向边(非横叉边)
} //三个值的最小值

【特殊情况】DFN(u)=Low(u)：以u为根的搜索子树上所有节点是一个强连通分量。搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量

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)
}