题解 P3388 【模板】割点（割顶）

wind_seeker · 2023-04-06 16:49:13 · 题解

• 定义

  • 割点：若删除某点以及其所有连边后，原本其所在图被分为至少两个图，这些图互相不能到达，则该点为割点。

  • 已遍历点：u 所在图中时间戳小于等于 u 的点。

• 做法：

  • tarjan 基础操作：

    • 取 dfn 值为 0 的点开始遍历，则对 dfn 和 low 进行赋值。

    • 访问 u 的儿子 v 。

    • 若 v 已经遍历，则 low[u]=min(low[u],dfn[v])。

    • 若 v 未曾遍历过，继续向 v 遍历，而后取 low[u]=min(low[u],low[v])。

  如果对于 v 已经遍历的情况不理解的话可以看后面难点。

  • 判断割点：

    • 若其为根，有至少两个子树，则其为割点。

    • 若 u 不为根但是 low_v\ge dfn_u 则其为割点。

• 证明：

  • 对于第一种割点，显然，两个子树只有根这么一条路。不过对于其儿子个数的判断，要小小讲一下。由于根可能会有几个儿子位于割去根后的同一个团中，而访问其中一个就可以通过遍历使这几个儿子的 dfn 都有值。所以只有当根扫到的儿子未被访问过时，才会有 child 的值加一。

  • 对于第二种割点，我们需要证明一下。我们假设遍历到了 u，low_v \ge dfn_u 表示儿子 v 点回溯可到达的最先点的时间戳大于等于 u 的时间戳，证明其不能通过 u 以外的点与已遍历点相连，那么意味着必然可以通过割去 u 而使得已遍历点与儿子 v 位于两个不互相连通的图。

下面即为图示过程：