割点。
RyexAwl
·
·
题解
0.前置知识
-
基本图论概念。
-
无向图的 DFS。
-
基本的递推 / DP 思想。
1.DFS 树
对于无向连通图 G=(V,E)，考虑按如下方式建立一个新的无向图 G'=(V,E')。规定其中 V=\{1,2,3,...,n\}。
void dfs(int x) {
vis[x] = true;
for (auto v : G[x]) {
if (vis[v]) continue;
ins_edge(x,v); // 将边 (x,v) 加入 E' 中
dfs(v);
}
}
从 [Tutorial] The DFS tree and its applications: how I found out I really didn't understand bridges 贺的动图。
性质 1.1： 图 G' 是树。
考虑以下代码：
void dfs(int x) {
vis[x] = true;
p[++ cnt] = x;
for (auto v : G[x]) {
if (vis[v]) continue;
ins_edge(x,v); // 在 dfs 树中加入边 (u,v)
father[v] = x;
dfs(v);
}
}
注意，**以固定节点为根建立的 DFS 树形态不唯一**。
**性质 1.2：** 对于所有非树边，在树上都是连接祖先和后代的。
贺来的图，可以结合图片理解该性质表达的意思，其中黑色加粗的边表示以 $1$ 为根建立的某棵 DFS 树上的边，未被加粗的边为 “非树边”：
考虑如果出现了 “横叉边” $(u,v)$（即 $u,v$ 在 DFS 树上并非祖先关系）：
设 $dfn_u<dfn_v$：
- 在遍历 $u$ 的出边时一定会遍历到边 $(u,v)$，如果此时 $v$ 未被访问（即 `vis[v] == false`）那么 $v$ 就会变成 $u$ 的儿子，与 $(u,v)$ 是横叉边矛盾。
- 可以推出如果 $(u,v)$ 是横叉边，那么在遍历到边 $(u,v)$ 时，$v$ 已经被访问过。又因为 $dfn_u<dfn_v$，所以在调用 `dfs(u)` 前未调用过 `dfs(v)`，根据 DFS 的过程，在出 $u$ 的子树前，不会访问 $u$ 子树外的点，所以可以推出 $v$ 在 $u$ 子树内，与 $(u,v)$ 是横叉边矛盾。
- 一个感性理解是对于一条边 $(u,v)$，如果 $dfn_u<dfn_v$，那么在遍历到边 $(u,v)$ 时如果 $v$ 未被访问那么 $v$ 是 $u$ 的儿子，否则因为 $u$ 的边还没遍历干净，根据 DFS 的过程，可以观察到此时有 $v$ 在 $u$ 子树内。
## 2.割点判定定理与 tarjan 算法
判断点 $x$ 是否是割点等价于考虑 $x$ 所在的连通块，删掉 $x$ 后连通块内的点是否连通，接下来只考虑一个连通块内的情况，即只考虑在一个无向连通图内判断点 $x$ 是否是割点。
接下来考虑在 DFS 树上确定 **非根** 节点 $x$ 是不是割点。不考虑非树边，删掉点 $x$ 后，树可以裂成若干个部分。
删掉 $x$ 后，只考虑树边的情况下有三个连通块 $A,B,C$，其中 $B,C$ 是 $x$ 儿子的子树，$A$ 是 $x$ 子树外的部分。
接下来考虑把非树边加进去，考察连通性。注意到，因为我们只在意连通性，所以我们并不在意 $A,B,C$ 内部的非树边，只在意 $A,B,C$ 之间的非树边。
根据 **性质 1.2**，建立 DFS 树后，所有非树边都是返祖边，所以 $A,B,C$ 之间的非树边，一定是 $B,A$ 之间和 $C,A$ 之间的边。
那么对于上面的图来说，在加入非树边后图连通的充要条件即 $B,A$ 之间存在返祖边且 $C,A$ 之间存在返祖边。
比如：
那么 $x$ 是割点当且仅当 $B,C$ 中有至少一棵子树与 $A$ 没边。
考虑更一般的情况，非根节点 $x$ 是割点当且仅当在 DFS 树上 $x$ 存在一个儿子 $y$ 满足 $y$ 子树内部的点与 $x$ 子树外的点没有边。
注意，之所以是非根节点，是因为当 $x$ 为根时，$A$ 为空，此时 $x$ 是割点等价于 $x$ 的儿子个数大于 $1$。
那么考虑维护哪些信息能够判定 $x$ 是否存在一个儿子 $y$ 满足 $y$ 子树内不存在连接 $x$ 子树外的边。
将所有非树边按从后代到祖先的方向定向，对于边 $(p,q)$，如果 $p$ 是 $q$ 的祖先称该边为从 $q$ 出发，终点为 $q$ 的返祖边。
注意到，对于 $x$ 的一个儿子 $y$，我们只在意从其子树内部出发终点深度最浅的返祖边。
如图，绿色的是起点和终点都在 $y$ 子树内部的返祖边，红色和橙色是从 $y$ 子树内部出发，终点为 $x$ 子树外的两条边（红色是从 $y$ 子树内部出发，终点深度最小的返祖边）。但是实际上对于 $y$ 子树内部的所有返祖边，我们可以只在意红色的那条。
考虑对每个点 $u$ 求出 DFS 树上以 $u$ 为根的子树内部点出发的所有返祖边中终点时间戳最小的时间戳（注意到，这里时间戳最小的点等价于深度最小的点），$low_u$。（当然这里其实可以直接定义为深度最小的点的深度（[定义为最小深度时的写法](https://www.luogu.com.cn/paste/s366knyv)），为了与目前流行的 tarjan 算法写法中的 low 数组定义一致，本文的主要内容使用该定义）
那么，我们不难得到 **性质 2.1（割点判定定理）**：对于 DFS 树上非根节点 $x$，点 $x$ 是割点当且仅当 $x$ 存在一个儿子 $y$ 满足 $low_y\ge dfn_x$，对于根节点 $rt$，$rt$ 是割点当且仅当存在大于 $1$ 个儿子 $y$ 满足 $low_y\ge dfn_x$。
那么接下来考虑如何计算 $low_u$，这里采用类似树形 DP 中自底向上递推的计算方法。如果 $u$ 有 $k$ 个儿子 $v_1,v_2,...,v_k$，那么可以把从 $u$ 子树内部出发的返祖边集合分为 $k+1$ 类，即从 $u$ 出发的和从 $v_1,v_2,...,v_k$ 子树内部出发的。对于前者直接遍历所有从 $u$ 出发的返祖边即可枚举，对于后者可以利用 $low_{v_i}$ 转移。
接下来考虑具体的算法实现。
为了方便实现，我们对代码中的 $\mathrm{low[u]}$ 的定义稍作调整，定义为从 $u$ 子树内出发的所有返祖边能走到的时间戳最小点的时间戳与 $dfn_u$ 和 $dfn_{fa_u}$ 取 $\min$ 的结果，其中 $fa_u$ 表示 $u$ 在 DFS 树上的父亲，特别的如果 $u$ 是根则只与 $dfn_u$ 取 $\min$。而这样的定义下，割点判定定理依然成立。
每个连通块的问题是独立的，找到每个未被访问过的连通块运行 tarjan 算法找割点：
```cpp
for (int i = 1; i <= n; i++) {
if (dfn[i]) continue;
tarjan(i,i);
}
```
其中函数 `tarjan(x,root)` 表示考虑以 $root$ 为根建立 $root$ 所在连通块的 DFS 树，当前访问到了点 $x$。
具体实现：
```cpp
void tarjan(int x,int root) {
dfn[x] = low[x] = ++ cnt; // 初始化时间戳与 low[x]。
int cnt = 0; // 计算有多少个儿子 v 满足 low[v] >= dfn[x]。
for (auto v : G[x]) {
if (!dfn[v]) {
tarjan(v,root); // 递归，按自底向上的顺序计算 low。
low[x] = min(low[x],low[v]); // 转移 low。
if (low[v] >= dfn[x]) ++ cnt; // 如果 low[v] >= dfn[x]，将 v 计入贡献。
} else {
low[x] = min(low[x],dfn[v]);
/* 转移所有从 x 出发的返祖边，注意这里遍历到的边有三类：
1. x 到 x DFS 树上父亲的边
2. 从 x 出发的返祖边
3. x 子树内部到 x 的返祖边
第三类边不会对 low[x] 产生贡献。
*/
}
}
// 割点判定定理
if (x == root) {
if (cnt > 1) ans.push_back(x);
} else {
if (cnt > 0) ans.push_back(x);
}
}
```
[P3388 【模板】割点（割顶），tarjan 求割点完整代码](https://www.luogu.com.cn/paste/m773icct)