寻找无向图的双连通分量（Biconnected Components） 题目描述 在无向图中，双连通分量（Biconnected Component）是指一个极大的双连通子图。双连通性意味着图中任意两个顶点之间至少存在两条顶点不相交的路径（即没有公共顶点）。双连通分量在图的连通性分析中非常重要，例如用于识别网络中的脆弱点（如割点）。题目要求：给定一个无向图，找出其所有双连通分量。 关键概念 割点（Articulation Point） ：移除该顶点后，图的连通分量数量增加。 桥（Bridge） ：移除该边后，图的连通分量数量增加。 双连通分量 ：不含割点的连通分量，或单个边（即使两端是割点）。 解题步骤 使用基于深度优先搜索（DFS）的算法，结合栈记录边，以高效找出双连通分量。 DFS遍历与记录信息 对每个顶点维护两个值： disc[u] ：DFS首次访问顶点 u 的时间戳（发现时间）。 low[u] ：从 u 出发通过DFS树边及一条回边能到达的最小 disc 值。 用栈存储遍历的边（而非顶点），以便在发现双连通分量时弹出边。 递归更新low值 对于当前顶点 u 及其邻居 v ： 若 v 未被访问（树边）： 将边 (u, v) 入栈。 递归访问 v ，更新 low[u] = min(low[u], low[v]) 。 检查 u 是否为割点：若 low[v] >= disc[u] ，则从栈中弹出边直到弹出 (u, v) ，这些边构成一个双连通分量。 若 v 已被访问且 v 不是 u 的父节点（回边）： 更新 low[u] = min(low[u], disc[v]) 。 若 v 的发现时间更早，将边 (u, v) 入栈（因回边可能属于双连通分量）。 处理根节点特殊情况 若 u 是DFS树的根，需额外检查：当根有多个子节点时，根才是割点。此时每棵子树独立形成双连通分量。 算法流程示例 假设无向图如下（边为1-2, 2-3, 3-4, 2-4, 2-5, 5-6）： 从顶点1开始DFS，栈中按顺序存入边。 当访问到边 (2, 5) 时，若发现 low[5] >= disc[2] ，则弹出边直到 (2, 5) ，得到分量{2, 5, 6}。 继续回溯，在顶点2处因 low[3] >= disc[2] ，弹出边直到 (1, 2) ，得到分量{1, 2, 3, 4}。 总结 通过DFS动态计算 low 值并利用栈管理边，可高效输出所有双连通分量。该算法时间复杂度为O(V+E)，适用于大规模无向图分析。