寻找图中的割点（Articulation Points）问题 题目描述 给定一个无向连通图，割点（或关节点）是指删除该顶点及其关联边后，图的连通分量数量增加的顶点。换句话说，割点是图中连接不同部分的关键顶点。我们需要设计一个算法，找出图中所有的割点。 解题过程 我们将使用基于深度优先搜索（DFS）的Tarjan算法来寻找割点。该算法通过DFS生成树和两个关键数组（ disc 和 low ）来识别割点。 步骤1：理解DFS生成树与关键数组 对图进行DFS遍历，会形成一棵DFS生成树（或森林）。 定义 disc[u] ：顶点 u 在DFS中被首次访问的时间（发现时间）。 定义 low[u] ：顶点 u 通过其子树中的回边（非树边）能够连接到的最早祖先的 disc 值。 割点条件： 若 u 是DFS树的根节点，且有两个或更多子树，则 u 是割点。 若 u 不是根节点，但其子节点 v 满足 low[v] >= disc[u] ，则 u 是割点。 步骤2：算法初始化 初始化全局变量 time ，记录DFS访问时间。 创建数组 disc 和 low ，初始化为 -1 （未访问）。 创建数组 parent ，记录DFS树中的父节点。 创建布尔数组 ap （Articulation Point），标记割点，初始为 false 。 步骤3：DFS遍历与更新规则 对每个未访问顶点 u 进行DFS： 设置 disc[u] = low[u] = ++time 。 遍历 u 的每个邻居 v ： 若 v 未访问： 设置 parent[v] = u 。 递归DFS访问 v 。 递归返回后，更新 low[u] = min(low[u], low[v]) 。 检查割点条件： 若 u 是根节点且有两个以上子树，标记 ap[u] = true 。 若 u 非根节点且 low[v] >= disc[u] ，标记 ap[u] = true 。 若 v 已访问且 v != parent[u] （处理回边），更新 low[u] = min(low[u], disc[v]) 。 步骤4：示例演示 考虑无向图：顶点集{0,1,2,3}，边集{(0,1),(1,2),(2,3),(3,0)}（一个环）。 从顶点0开始： disc[0]=0, low[0]=0 ，访问邻居1（未访问）。 递归到1： disc[1]=1, low[1]=1 ，访问邻居2（未访问）。 递归到2： disc[2]=2, low[2]=2 ，访问邻居3（未访问）。 递归到3： disc[3]=3, low[3]=3 ，访问邻居0（已访问且非父节点2），更新 low[3]=min(3,0)=0 。 回溯到2：更新 low[2]=min(2,0)=0 ，检查 low[3]=0 < disc[2]=2 ，不标记割点。 回溯到1：更新 low[1]=min(1,0)=0 ，检查 low[2]=0 < disc[1]=1 ，不标记割点。 回溯到0：检查根节点0的子树数量（1棵），不标记割点。 结果：该图无割点（符合环的性质）。 步骤5：算法复杂度与注意事项 时间复杂度：O(V + E)，其中V为顶点数，E为边数。 空间复杂度：O(V)（存储数组和递归栈）。 注意：处理重边时，算法仍有效，因回边条件 v != parent[u] 已排除父边。 通过以上步骤，我们可以系统地找出图中所有割点，确保图的连通性分析准确无误。