无向图的双连通分量（Biconnected Components）

问题描述
在无向连通图中，若删除任意一个顶点后图仍保持连通，则该图是双连通的。双连通分量是极大的双连通子图，用于识别图中的“脆弱点”（即割点）。例如，在通信网络中，双连通分量帮助定位单点故障风险。本问题要求找出图中所有双连通分量。

解题步骤
1. 核心概念理解

• 割点（Articulation Point）：删除该顶点后，图的连通分量数增加。
• 桥（Bridge）：删除该边后，图的连通分量数增加。
• 双连通分量：不含割点的极大连通子图，分量内任意两点存在两条边不相交的路径。

2. 算法选择：基于DFS的Tarjan算法
通过一次DFS遍历，记录每个顶点的发现时间（disc）和通过回边能到达的最小发现时间（low），并利用栈存储边。

3. 算法步骤详解

• 初始化：

  • 为每个顶点维护 disc[u]（DFS首次访问时间）、low[u]（通过回边能回溯到的最早祖先）。
  • 初始化全局时间戳 time = 0 和空栈 stack。
  • 对未访问顶点调用DFS。

• DFS遍历：

  1. 设置 disc[u] = low[u] = ++time。
  2. 遍历邻接顶点 v：
     • 若 (u, v) 是未访问树边：
       • 将边 (u, v) 压栈，递归访问 v。
       • 更新 low[u] = min(low[u], low[v])。
       • 检查割点条件：
         • 若 low[v] >= disc[u]，则 u 是割点（根节点需至少两个子节点）。此时从栈中弹出边，直到弹出 (u, v)，这些边构成一个双连通分量。
     • 若 v 已访问且 v 不是父节点：
       • 更新 low[u] = min(low[u], disc[v])。
       • 若 v 的发现时间更早，将边 (u, v) 压栈（处理回边）。

• 处理剩余边：
  DFS完成后，若栈中还有边，剩余边属于最后一个双连通分量。

4. 示例演示
考虑无向图：

边集: (0,1), (1,2), (2,0), (1,3), (3,4), (4,5), (5,3)

• 从顶点0开始DFS，识别割点：
  • 顶点1是割点（删除1后图不连通）。
  • 双连通分量：
    • 分量1: 边 {(0,1), (1,2), (2,0)}（三角形环）。
    • 分量2: 边 {(1,3), (3,4), (4,5), (5,3)}（环3-4-5）。

5. 关键点注意

• 割点可能属于多个双连通分量，但边仅属于一个分量。
• 算法时间复杂度为 O(V+E)，与DFS相同。

总结
通过Tarjan算法的一次DFS遍历，结合栈管理边，可高效分解无向图为双连通分量，应用于网络鲁棒性分析、电路设计等领域。