寻找无向图中的割点（Articulation Points）

题目描述
给定一个无向连通图 \(G = (V, E)\)，其中 \(V\) 是顶点集，\(E\) 是边集。割点（或关节点）是指：如果删除该顶点及其关联的边，会导致图的连通分量数量增加。换句话说，移除割点后，原图会变得不连通（或连通分量数增加）。
任务是找出图中所有的割点。

解题过程循序渐进讲解
我将通过一个经典算法（基于深度优先搜索，即DFS）来求解，步骤会详细展开。

第一步：理解割点的定义与性质
考虑一个无向连通图，割点可能出现在两种情况下：

1. 如果该顶点是DFS生成树的根节点，并且它有两个或更多个子树（即，在DFS树中，根有至少两个子节点），那么该根节点是割点。
2. 如果该顶点不是根节点，但它有一个子节点，使得这个子节点及其后代无法通过回边（back edge）到达该顶点的祖先，那么该顶点是割点。
   更形式化地说：设 \(u\) 是一个非根顶点。如果存在 \(u\) 的一个子节点 \(v\)，使得以 \(v\) 为根的DFS子树中，所有顶点能访问到的最早祖先（即通过回边能到达的最小发现时间）不小于 \(u\) 的发现时间，则 \(u\) 是割点。

第二步：引入关键概念与变量
我们需要在一次DFS遍历中记录以下信息：

• disc[u]：顶点 \(u\) 的发现时间（DFS第一次访问到 \(u\) 的时间戳），从1开始递增。
• low[u]：顶点 \(u\) 能够通过其DFS子树中的回边（即不经过父边）访问到的最小发现时间。
  更准确地说，low[u] 是以下三者的最小值：
  (1) disc[u]（自身）
  (2) 对于 \(u\) 的每个邻接顶点 \(v\)，如果 \(v\) 是 \(u\) 在DFS树中的子节点，则考虑 low[v]（即通过子树的后向边）
  (3) 对于 \(u\) 的每个邻接顶点 \(v\)，如果 \(v\) 不是 \(u\) 的父节点，且已被访问过（即回边），则考虑 disc[v]
• parent[u]：在DFS生成树中，\(u\) 的父节点（根节点的父节点为 -1）。
• 一个布尔数组 isAP[] 标记顶点是否为割点。

第三步：算法步骤（递归DFS）

1. 初始化：

   • 时间戳 time = 0
   • disc[] 初始化为 -1（表示未访问）
   • low[] 和 parent[] 可初始化为 0 或 -1
   • isAP[] 初始化为 false

2. 对图中每个未访问顶点进行DFS（因为图连通，只需从任意起点开始一次DFS即可，但如果图不连通，需对每个连通分量分别处理）：

   • 调用DFS函数 dfs(u, parent)

3. DFS函数 dfs(u, parent) 的逻辑：
   a. 设置 disc[u] = low[u] = ++time
   b. 初始化子节点数 children = 0（在DFS树中）
   c. 对于每个邻接顶点 v：

   • 如果 v 未被访问（即 disc[v] == -1）：
     • 递归调用 dfs(v, u)
     • 更新 low[u] = min(low[u], low[v])
     • 增加 children 计数
     • 判断割点条件：
       情况1：如果 u 是根节点（parent == -1）且 children >= 2，则 u 是割点。
       情况2：如果 u 不是根节点，且 low[v] >= disc[u]，则 u 是割点。
       • 解释：low[v] >= disc[u] 意味着 v 及其子树无法通过回边到达 u 的祖先，所以删除 u 后，v 的子树将与图的其他部分断开。
   • 如果 v 已被访问，且 v 不是父节点（即 v != parent），则 (u, v) 是一条回边，更新 low[u] = min(low[u], disc[v])

4. 遍历所有顶点，输出 isAP[u] 为 true 的顶点，即为所有割点。

第四步：举例说明
考虑一个简单无向图：顶点 {0,1,2,3}，边为 (0,1), (1,2), (2,0), (1,3)。
从顶点0开始DFS，假设顺序为 0 → 1 → 2 → 3。

• 访问0: disc[0]=1, low[0]=1, children=1（子节点1）
• 访问1: disc[1]=2, low[1]=2, children=2（子节点2和3）
• 访问2: disc[2]=3, 邻接点0已访问且不是父节点（0≠1），更新 low[2] = min(3, disc[0]=1) = 1。回溯到1，更新 low[1] = min(2, low[2]=1) = 1。
• 访问3: disc[3]=4, 邻接点只有1（已访问，是父节点），无其他邻接点，回溯。
  检查割点：
• 顶点1（非根）：子节点3的 low[3]=4 >= disc[1]=2 成立，所以1是割点。删除1后，图变成 {0,2} 和 {3} 两个连通分量。
• 根节点0：子节点数=1，不满足 children>=2，不是割点。
  结果：割点为 {1}。

第五步：复杂度与注意事项

• 时间复杂度：O(V + E)，因为算法本质上是对图的DFS遍历，每条边和每个顶点访问常数次。
• 空间复杂度：O(V) 用于存储数组和递归栈（最坏情况 O(V)）。
• 注意：算法假设图是无向的。如果图不连通，需要对每个连通分量分别运行算法（即多次DFS）。

第六步：边界情况

• 图只有1个顶点：没有割点（删除后无顶点，不增加连通分量数）。
• 图是树：所有非叶子顶点都是割点（根节点若只有1个子节点则不是割点）。
• 图是环：没有割点（删除任意顶点仍连通）。

第七步：实现伪代码

function findArticulationPoints(G):
    V = 图中顶点数
    disc[V] = {-1}, low[V] = {0}, parent[V] = {-1}
    isAP[V] = {false}
    time = 0

    function dfs(u, parent):
        disc[u] = low[u] = ++time
        children = 0
        for each v in G.adj[u]:
            if disc[v] == -1:  # 未访问
                children++
                parent[v] = u
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if parent[u] == -1 and children >= 2:
                    isAP[u] = true
                if parent[u] != -1 and low[v] >= disc[u]:
                    isAP[u] = true
            else if v != parent:  # 回边
                low[u] = min(low[u], disc[v])

    for each vertex u in G:
        if disc[u] == -1:
            dfs(u, -1)
    return isAP

第八步：验证
可以选取不同结构的图（如星形、链状、完全图等）手动模拟算法，确认输出符合割点定义。

通过以上步骤，你应该能够理解如何通过一次DFS找出无向图中的所有割点，并可以尝试编码实现。