Tarjan算法求无向图的割点（Articulation Points） 题目描述 给定一个无向连通图，割点（Articulation Point）是指删除该顶点及与其相连的边后，图不再连通的顶点。要求高效找出图中所有割点。例如，在计算机网络中，割点可能代表关键节点，其故障会导致网络分裂。Tarjan算法通过一次深度优先搜索（DFS）即可解决此问题。 解题过程 核心概念 割点判定条件 ：在DFS生成树中，对非根节点 u ，若存在子节点 v 满足 low[v] >= disc[u] ，则 u 是割点（ v 无法通过回边到达 u 的祖先）；对根节点，若拥有多于一个子树则为割点。 发现时间（disc） ：记录顶点在DFS中首次被访问的顺序。 最低访问时间（low） ：记录顶点通过DFS树边和回边能到达的最小 disc 值。 算法步骤 初始化 ：为每个顶点维护 disc 和 low 数组，初始化为-1（未访问），设置全局时间计数器 time 。 DFS遍历 ：从任意顶点开始DFS，递归访问邻接点： 访问顶点 u 时，记录 disc[u] = low[u] = ++time 。 遍历 u 的邻接点 v ： 若 v 未访问： 递归处理 v ，更新 low[u] = min(low[u], low[v]) 。 回溯后检查：若 u 非根且 low[v] >= disc[u] ，则 u 是割点。 若 u 是根节点，统计子树数量，子树数≥2时标记为割点。 若 v 已访问且不是父节点（处理回边），更新 low[u] = min(low[u], disc[v]) 。 根节点特殊处理 ：在DFS开始时，若根节点有多个子树，直接标记为割点。 实例演示 考虑图：顶点集{0,1,2,3}，边集{(0,1),(1,2),(2,3),(3,0)}（一个环）。 从顶点0开始DFS： 访问0（disc=0），递归访问1（disc=1）、2（disc=2）、3（disc=3）。 顶点3的邻接点0已访问（回边），更新 low[3] = min(low[3], disc[0]) = 0 。 回溯至2： low[2] = min(low[2], low[3]) = 0 ，同理更新1和0的low值。 所有顶点均满足 low[v] < disc[u] ，且根节点0只有一个子树，故无割点。 若添加边(1,3)形成完整图，仍无割点；若删除边(0,3)，则顶点1和2成为割点。 复杂度分析 时间复杂度：O(V+E)，每个顶点和边仅处理一次。 空间复杂度：O(V)，用于存储 disc 、 low 、父节点数组和DFS栈。 关键点 利用DFS树区分树边和回边，通过 low 值传递判断连通依赖性。 根节点需单独处理，仅依赖子树数量统计。