xxx 无向图的双连通分量（Biconnected Components） 题目描述 在无向图中，双连通分量（Biconnected Components）是极大的双连通子图。双连通性意味着图中任意两个顶点之间存在至少两条顶点不相交的路径（即没有割点）。本问题要求找出无向图中所有的双连通分量，并识别图中的割点（Articulation Points）。 解题过程 核心概念理解 割点 ：移除该顶点后，图的连通分量数增加。 桥 ：移除该边后，图的连通分量数增加。 双连通分量 ：不含割点的极大连通子图，分量内任意两点至少通过两条不相交路径相连。 算法选择：基于DFS的Tarjan算法 通过一次DFS遍历，记录每个顶点的 发现时间 （ disc ）和 低链接值 （ low ）。 低链接值 low[u] ：从顶点 u 出发，通过DFS树边和后向边能访问到的最早顶点（最小 disc 值）。 使用栈存储遍历边，用于输出双连通分量。 详细步骤 步骤1：初始化 定义全局变量： disc[] ：记录顶点的发现时间。 low[] ：记录顶点的低链接值。 parent[] ：记录DFS树中的父节点。 栈 stack ：临时存储当前分量的边。 初始化所有 disc 和 low 为 -1 （未访问）。 步骤2：DFS遍历 对每个未访问顶点 u ： 设置 disc[u] = low[u] = ++time 。 遍历邻接顶点 v ： 若 v 未访问： 将边 (u, v) 压入栈。 设置 parent[v] = u ，递归访问 v 。 回溯时更新： low[u] = min(low[u], low[v]) 。 割点判定 ：若 low[v] >= disc[u] 且 u 非根节点，则 u 是割点。 双连通分量输出 ：若 low[v] >= disc[u] ，从栈中弹出边直到 (u, v) ，这些边构成一个双连通分量。 若 v 已访问且 v != parent[u] ： 更新 low[u] = min(low[u], disc[v]) ，若 disc[v] < disc[u] 则将边 (u, v) 压栈。 步骤3：根节点特殊处理 若根节点在DFS树中有超过一个子节点，则根节点是割点。 实例演示 考虑无向图：顶点集 {0,1,2,3}，边集 {(0,1), (1,2), (2,3), (3,1)}。 从顶点0开始DFS： 访问顺序：0→1→2→3。 回溯时发现 low[3] = disc[1] ， low[2] = disc[1] ， low[1] = disc[1] 。 顶点1满足 low[2] >= disc[1] ，是割点。 输出双连通分量：边集 {(1,2), (2,3), (3,1)} 和 {(0,1)}。 复杂度分析 时间复杂度：O(V + E)，与DFS相同。 空间复杂度：O(V) 存储数组，O(E) 存储栈。 关键点总结 割点判定依赖子节点的 low 值是否不小于当前节点的 disc 值。 栈中边的弹出时机由割点触发，确保分量的完整性。 根节点需单独判断子节点数以确定是否为割点。