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

题目描述
给定一个无向连通图，找出其所有的双连通分量（Biconnected Components）。双连通分量是图的一个极大双连通子图，即删除其中任意一个顶点后，子图仍然连通。若整个图是双连通的，则其本身就是一个双连通分量。双连通分量常用于分析网络的鲁棒性。

解题过程

1. 基本概念

• 割点（Articulation Point）：删除该顶点后，图不再连通的顶点。
• 桥（Bridge）：删除该边后，图不再连通的边。
• 双连通分量：不含割点的极大连通子图，或由一条边连接两个割点构成的子图（如一条桥边）。

关键性质：双连通分量中的任意两点至少存在两条顶点不相交的路径。

2. 算法思路（基于DFS）
使用DFS遍历图，并维护以下信息：

• disc[u]：顶点u的发现时间（DFS首次访问的时间戳）。
• low[u]：从u出发通过DFS树边或后向边能到达的最小发现时间。
• 用一个栈保存遍历过程中的边，遇到割点或桥时弹出栈中边，形成一个双连通分量。

算法步骤：

1. 从任意顶点开始DFS，初始化时间戳time=0。

2. 对当前顶点u，遍历其邻居v：

   • 若v未被访问：
     • 将边(u,v)入栈。
     • 递归访问v，更新low[u] = min(low[u], low[v])。
     • 若low[v] >= disc[u]，则u是割点（根节点需特殊判断），此时从栈中弹出边直到(u,v)，这些边构成一个双连通分量。
   • 若v已被访问且v不是u的父节点（说明(u,v)是后向边）：
     • 更新low[u] = min(low[u], disc[v])。
     • 若v的发现时间更早，将边(u,v)入栈（避免重复需判断disc[v] < disc[u]）。

3. 根节点是割点的条件：DFS树中有至少两个子节点。

3. 详细示例
考虑无向图：

0---1---2
|  /|  /|
| / | / |
3---4---5

步骤：

• DFS从顶点0开始，记录发现时间和low值。
• 当遍历到边(1,4)时，发现low[4] >= disc[1]，顶点1是割点，弹出栈中边直到(1,4)，得到双连通分量{0,1,3,4}。
• 继续遍历，遇到其他割点（如顶点4）时类似操作，最终得到全部分量：
  • {0,1,3,4}
  • {1,2,4}
  • {4,5}

4. 算法实现要点

• 使用栈保存边而非顶点，因为双连通分量可能共享顶点（割点）。
• 时间复杂度O(V+E)，与DFS相同。
• 割点判断条件：
  • 非根节点u：存在子节点v使low[v] >= disc[u]。
  • 根节点u：DFS树中有≥2个子节点。

5. 应用场景

• 网络容错分析：识别关键节点（割点）。
• 图压缩：将双连通分量缩为一个顶点，简化图结构。
• 电路设计：确保电路部分模块的稳定性。

通过以上步骤，可系统性地分解无向图的双连通分量，并理解其结构特性。