Tarjan算法：求解图的割点与桥

tarjan可以用来求割点，割边，也可以求强联通图， 重连通图。

注意强连通图是有向图，重联通图是无向图里的。

摘自

在具体实现Tarjan算法上，我们需要在DFS（深度优先遍历）中，额外定义三个数组dfn[]，low[]，parent[]

dfn数组

dnf数组的下标表示顶点的编号，数组中的值表示该顶点在DFS中的遍历顺序(或者说时间戳)，每访问到一个未访问过的顶点，访问顺序的值（时间戳）就增加1。子顶点的dfn值一定比父顶点的dfn值大（但不一定恰好大1，比如父顶点有两个及两个以上分支的情况）。在访问一个顶点后，它的dfn的值就确定下来了，不会再改变。

stamp = 0
stamp_dict = {}
def dfs(u):
    stamp_dict[u] = stamp
    stamp += 1
    for v in Graph[u]:
        dfs(v)

low数组

low[u]表示u这个点能够连通到的所有的点的时间戳的最小值。时间戳越小说明在搜索树当中的位置越高，也可以理解成u能够连通到的处在搜索树中最高的点。那么很明显了，这个点就是u这个点所在强连通分量所在搜索树某一棵子树的树根。

割点及桥的判定方法

割点：判断顶点U是否为割点，用U顶点的dnf值和它的所有的孩子顶点的low值进行比较，如果存在至少一个孩子顶点V满足low[v] > dnf[u]，就说明顶点V访问顶点U的祖先顶点，必须通过顶点U，而不存在顶点V到顶点U祖先顶点的其它路径，所以顶点U就是一个割点。对于没有孩子顶点的顶点，显然不会是割点。

桥（割边）：low[v] > dnf[u] 就说明V-U是桥

tarjan实现，及求强连通图

tarjan实现

求重连通分量：dfn就是个时间戳，用stamp表示。 stack作为栈记录访问的节点，即可以用来判断是否访问过来更新low[u]也可以用来记录重连通分量找到树根.

这里只能用栈作为访问标记不能用visit， 因为多重连通分量的情况下会有问题。

树根特点: dfn[u] == low[u]

scc = []
stack = []
low = []
dfn = []

def tarjan(u):
    dfn[u], low[u] = stamp, stamp
    stamp += 1
    stack.append(u)
    
    for v in Graph[u]:
        if not dfn[v]:
            tarjan(v)
            low[u] = min(low[u], low[v])
        elif v in stack:
            low[u] = min(low[u], dfn[v])
    
   if dfn[u] == low[u]:
        cur = []
        # 栈中u之后的元素是一个完整的强连通分量
        while True:
            cur.append(stack[-1])
            stack.pop()
            if cur[-1] == u:
                break
        scc.append(cur)