割点和割边(cut Vertex and cut edge)

组别：提高级
难度：7

割点是指在一个连通图中，删除该点及其关联的边后，图的连通分量数增加的顶点。换句话说，如果删除一个顶点使得原来的连通图变成不连通或连通分量增加，则该顶点称为割点。

割边是指在一个连通图中，删除该边后，图的连通分量数增加的边。换句话说，如果删除一条边使得原来的连通图变成不连通或连通分量增加，则该边称为割边。

计算方法

为了找出图中的割点和割边，可以使用深度优先搜索（DFS）算法。具体步骤如下：

• 割点：
  • 初始化DFS树，记录每个顶点的发现时间和最低时间（Low值）。
  • 在DFS过程中，通过更新Low值来判断是否存在割点。
  • 如果某个顶点u存在一个子节点v，满足条件：Low[v] ≥ Discovery[u]，则u是割点。
• 割边：
  • 类似地，在DFS过程中，通过比较发现时间和Low值来判断是否存在割边。
  • 如果某条边(u, v)满足条件：Low[v] > Discovery[u]，则(u, v)是割边。