寻找无向图的双连通分量（Biconnected Components） 题目描述 在无向图中，双连通分量（Biconnected Components）是指一个极大的子图，其中任意两个顶点之间至少存在两条顶点不相交的路径（即没有割点）。双连通分量在网络设计、电路板布线等领域有重要应用。题目要求：给定一个无向图，找出其所有的双连通分量。 关键概念 割点（Articulation Point） ：若删除该顶点后图不再连通，则该顶点为割点。 桥（Bridge） ：若删除某条边后图不再连通，则该边为桥。 双连通分量 ：要么是单个边（如两个顶点由一条边连接），要么是一个不含割点的极大连通子图。 解题步骤 使用基于DFS的Tarjan算法变种，通过维护每个顶点的发现时间（discovery time）和低链接值（low-link value）来识别双连通分量。 初始化 为每个顶点维护以下属性： disc[u] ：顶点 u 的发现时间（DFS首次访问的时间戳）。 low[u] ：从 u 出发通过DFS树能回溯到的最早顶点的时间戳（包括反向边）。 parent[u] ：DFS树中 u 的父节点。 使用栈存储当前DFS路径中的边。 全局变量 time 记录时间戳。 DFS遍历与低链接值计算 从任意未访问顶点开始DFS。 对当前顶点 u ： 初始化 disc[u] = low[u] = ++time 。 遍历 u 的邻居 v ： 若 v 未访问： 将边 (u, v) 入栈。 设置 parent[v] = u ，递归访问 v 。 回溯时更新： low[u] = min(low[u], low[v]) 。 关键判断 ：若 low[v] >= disc[u] ，则 u 是割点（根节点需特殊处理），此时栈中从栈顶到边 (u, v) 的所有边属于一个双连通分量。 若 v 已访问且 v != parent[u] （即反向边）： 更新 low[u] = min(low[u], disc[v]) ，若 v 的发现时间更早，则将边 (u, v) 入栈（因可能属于同一分量）。 处理根节点 若 u 是DFS树的根节点，只需检查其子节点数：若有至少两个子节点，则根节点是割点。 输出双连通分量 每当检测到割点或桥时，从栈中弹出边直到当前边 (u, v) ，这些边构成一个双连通分量。 示例 考虑无向图：顶点集{0,1,2,3}，边集{(0,1), (1,2), (2,0), (1,3)}。 DFS从顶点0开始： 访问顺序：0→1→2→3。 当回溯到顶点1时，发现 low[2] >= disc[1] ，说明边(1,2)、(2,0)、(0,1)构成一个双连通分量（三角形）。 边(1,3)作为另一个双连通分量（桥）。 复杂度分析 时间复杂度：O(V+E)，与DFS相同。 空间复杂度：O(V+E)用于存储栈和DFS递归栈。 通过此算法，可高效分解无向图的双连通分量，辅助分析图的连通性结构。