这篇文章会介绍寻找无向图中的点双连通分量算法，由于要用到Tarjan算法相关的前辈知识，建议先阅读这篇介绍Tarjan算法的文章再来阅读。

双连通分量分为点双连通和边双连通。

点双连通是指这个一个无向图的极大子图，删掉任意一个节点后，子图仍然连通。边双连通分量定义类似，就是改为去掉任意一条边。

一般在实际应用中，点双连通分量最常用。

寻找双连通分量算法最核心的判定法则：

在DFS过程中，对于边(u, v), low[v] >= dfn[u]

如何理解这个条件呢？

我们知道low[v]是指顺着v往下走可以到达的最早的节点。如果 low[v] < dfn[v]。就意味着存在一个环，从v点出发可以到达v的上游。

而对于边(u, v)，如果low[v] >= dfn[u], 就说明 v 无法跳过 u 达到更早的祖先，这个时候，u就是一个潜在的割点。一旦u消失，那么v这一部分就和上游节点隔离了。

由此可以给出对应的算法框架：

Algorithm: Find_vBCC_Components(graph)
Input: a undirected graph stored in adj
Output: a array BCC_List where each item is a set of vertices in same BCC

Fn Find_vBCC_Components(graph)
    init an empty array BCC_List
    init dfn[], low[] (all set to 0 )
    init a stack Q
    init timer=0

    for each vertex u in G:
        if (dfn[u]==0):
            DFS_vBCC({G,u,NULL}) // {graph, vertex, parentVetex}
        endif
    endfor

    return BCC_List

Procedure DFS_vBCC({G,u,p})
    timer++
    dfn[u]=low[u]=timer

    for each vertex v in G.adj[u]:
        if(v==p):
            continue  // 跳过指向父节点的边
        endif

        if(dfn[v]==0):
            S.push(edge(u, v))
            DFS_vBCC({G,v,u})
            low[u]=min(low[u], low[v])

            if(low[v] >= dfn[u]):
                Start new BCC
                Repeat:
                    edge(m,n) = S.pop()
                    append m,n to BCC
                Until: (m,n)=(u,v)
                BCC_List.append(BCC)
            endif
        else if (dfn[v] < dfn[u]):  // 找到一条反向边
            S.push(edge(u, v))
            low[u]=min(dfn[v],low[u])
        endif
    endfor

这里的DFS和 Tarjan 算法有个关键的差别：栈中存储的是边，而不是点。

这是因为一个点可能属于多个双连通分量，如果存储点的话，构建新BCC的最后一步就会将点从栈中弹出，其他双连通分量就无法找到了。

我们可以以一个例子来理解这个过程：

     E -- D
     |    |
A -- B -- C

从A点开始DFS,栈中逐渐加入 A, B, C, D, E.

当处理E时，会发现B点是祖先节点，所以会更新自己的low值。递归回溯的过程中，D, C, B的low值都会被更新，并且D, C 过程中low值都比自己的dfn值要小，不会有任何处理。

但是到了B点，会发现low值和dfn值相等，于是就找到了一个双连通分量。他会将这几条边弹出栈：(E,B) (D, E) (C, D) (B, C)。这就找到了一个双连通分量。

然后退回到A点，发现low值和dfn值又相等，于是又得到一个双连通分量{A, B}

这样，就对双连通分量的算法运行过程有了一个比较直观的理解。