给定一张 n 个点 m 条边的无向图，求最少去掉多少个点，可以使图不连通。 如果不管去掉多少个...

下面的内容尝试“极致深度”地剖析题目与代码背后的核心思路及其实现细节，力求在原理、算法设计与代码实现三个层面都做深度探讨。

---

1. 问题背景与本质

题目要求：在给定的无向图中，最少删除多少个点，使图变得不连通？若无论删除多少点都无法让图不连通（比如完全图等极端情况），就返回 $n$。

• 「最少删除多少点使图不连通」在图论中就是求图的点连通度（Vertex Connectivity），即： $$\kappa(G) = \min_{S \subseteq V(G),\, G-S \text{不连通}} |S|.$$
• 当图的所有点都必须被删除才能让图不连通时，$\kappa(G)=n$。

1.1 与边割 (Edge Cut) 相对的概念

• 常见的「用最大流最小割算法求连通度」思路，通常是把边的容量和最小割联系起来（即边连通度 $\lambda(G)$）；但本题要找的是点割（vertex cut）而非边割。所以需要运用**“点拆分”技巧，将点容量转化为边容量**进行最大流最小割。

1.2 最小点割与最大流最小割定理

• 根据图论中Mader定理以及后续发展出的结论：无向图的点连通度也可以通过把每个点拆分成两个点，用一条容量为1的边连接它们，然后把原图中的无向边变成容量无限（或很大）的边进行连接，从而将对「点的切除」转化为对那条容量1的「边的切除」。
• 对每对顶点 $(s, t)$ 做最大流最小割，可以得到从 $s$ 到 $t$ 的点连通度。图整体的点连通度，是对所有顶点对 $(s, t)$ 的最小值： $$\kappa(G) = \min_{s \neq t} \Big(\text{mincut}(s, t)\Big).$$
• 如果能用少于$n$个点就把某两个点分开了，那对应的割值就会小于$n$；反之，如果对任何一对 $(s, t)$ 进行最小割都 $\geq n$，说明要想分开这两个点至少要割掉$n$条“容量为1的边”，也就意味着至少得删除$n$个点（即所有点）。所以最终得到的答案若仍是$n$，便表示必须全删才能让图不连通。

---

2. 思路的核心：点拆分 + 最大流最小割

2.1 点拆分（Vertex Splitting）

对每个点 $i$，把它拆分成两个点：

1. “入点”$i_{in}$（代码中对应 i），
2. “出点”$i_{out}$（代码中对应 n + i）。

在“入点”和“出点”之间连一条容量为1的有向边：

$$i_{in} \longrightarrow i_{out},\quad \text{capacity}=1.$$

这条容量1的边就对应**“删除点 i 的代价是1”**。如果要在最小割中“切”掉点 $i$，就等价于割掉这条容量1的边。

2.2 原无向边的处理

原无向图中的一条边 $(x, y)$ 转化为两条有向边：

$$x_{out} \longrightarrow y_{in},\quad \text{capacity}=\infty$$ $$y_{out} \longrightarrow x_{in},\quad \text{capacity}=\infty$$

用容量无穷（或一个非常大的值，代码中以 INF 表示）模拟原无向边。为什么要容量无限？因为我们不希望在最小割时“切”这条边来节省容量——切这条边无收益，因为题目要付出“删除点”的代价。只有切拆点边（容量1那条）才能模拟“删除该顶点”的行为。因此，通过把顶点与顶点之间的原图连线变成“无限容量”，就可以防止最小割优先割边；真正的“开销”集中在点本身上（也就是那条容量1的“入点-出点”边）。

2.3 对每对 $(s, t)$ 求最小割

• 接下来，对图中每对不同顶点 $(i, j)$，把源点 $S$ 设置为 $i_{out} = n+i$，把汇点 $T$ 设置为 $j_{in} = j$。
• 利用最大流-最小割算法（Dinic 或 Edmond-Karp等）求出这张“拆点图”从 $i_{out}$ 到 $j_{in}$ 的最小割。
• 该最小割的容量值就是把 $i$ 和 $j$ 两点分到不同连通分量中时，最少需要删除的点数。

为什么选 $S = i_{out}$ 和 $T = j_{in}$ 而不是反过来？

• 实际上选 $(i_{in}, j_{out})$ 或者 $(i_{out}, j_{in})$ 等都可以，只要保证「源点」和「汇点」对应了拆点后不重合的两个端即可。
• 代码中做法往往是：源点选 $i_{out}$，汇点选 $j_{in}$，这样在最小割时，如果想阻隔 $i_{out}$ 到 $j_{in}$ 这条路径，就需要割去某些容量1的“顶点边”，这对应删除那些点。

2.4 多对 $(s,t)$ 取最小值

• 对所有点对 $(i,j)$, $i<j$ 循环，依次用最大流最小割算出一个割值。取这些割值的最小值即为整张图的点连通度。
• 若所有对 $(i,j)$ 之间的最小割都是 $\ge n$（即无论割什么，都必须删 $n$ 个点才能把它们分开），则返回 $n$。

---

3. 代码实现的要点剖析

下面结合你给出的代码，重点解析它如何一步步实现上述逻辑。

3.1 建图部分

cpp
// 全局数组和常量
const int N = 110, M = 5210, INF = 1e8; // N与M是可容纳的最大节点数与边数
int n, m, S, T;                       // n和m分别是点和边, S是源, T是汇
int h[N], e[M], f[M], ne[M], idx;     // 邻接表头h[]，存储边目标节点e[]，容量f[]，下一条边ne[], idx是边编号

1. h[u] 表示从顶点 $u$ 出发的第一条边在边数组中的编号。
2. e[i] 表示第 $i$ 条边所通向的目标顶点；f[i] 表示第 $i$ 条边的剩余容量；ne[i] 表示边表中与第 $i$ 条边同起点的下一条边的编号；idx 用来给边编号。

双向建图：在 Dinic 中，每次加一条容量为 $c$ 的边，就会配合加一条容量为 0 的反向边（这样才能在流走了之后实现退流的可能）。

cpp
void add(int a, int b, int c)
{
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++;
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++;
}

• 这里可以看到每次调用 add(a,b,c)，就添加了两条记录：
  • 正向：从 $a$ 到 $b$，容量 c
  • 反向：从 $b$ 到 $a$，容量 0
• 这样就能支持增广流时的退流操作。

3.1.1 给每个点拆分成 in、out

cpp
for (int i = 0; i < n; i ++ )
    add(i, n + i, 1);

这就是对每个点 $i$ 做了：

• i 表示 $i_{in}$
• n+i 表示 $i_{out}$
• 设置容量 = 1，即割掉这条边就相当于删除顶点 $i$。

3.1.2 读入无向边并设置容量无限

cpp
while (m -- )
{
    int a, b;
    scanf(" (%d,%d)", &a, &b);
    add(n + a, b, INF);
    add(n + b, a, INF);
}

• 把无向边 $(a,b)$ 分成两条有向边：
  • $a_{out} \to b_{in}$ (add(n + a, b, INF))
  • $b_{out} \to a_{in}$ (add(n + b, a, INF))
• 容量设成 INF，模拟“不会去割这条边来实现分割”，只有点自己的那条容量=1的边才是最有可能被割掉的地方。

3.2 Dinic 最大流算法流程

代码使用了典型的 Dinic 最大流模板：

1. bfs()：在残量网络上找出分层图（level graph）。
2. find(u, limit)：在分层图中从节点 u 出发，用DFS尽量增广，找出阻塞流（blocking flow）。
3. 不断循环执行 BFS + DFS 直到无法增广。

这里不细讲 Dinic 的标准逻辑，而是强调为什么要在每组 $(S,T)$ 之间都做 Dinic——因为我们要在同一张构造好的容量网络里，尝试从某个顶点对 $(i_{out}, j_{in})$ 找最小割。Dinic 返回的就是最大流，而由最大流-最小割定理可知，最大流值 = 最小割容量。

3.3 代码核心：对所有点对 $(i,j)$ 取最小

cpp
int res = n;
for (int i = 0; i < n; i ++ )
    for (int j = 0; j < i; j ++ )
    {
        S = n + i, T = j;
        // 重置流量（退回流量，把所有边的f[k]恢复到原始剩余容量）
        for (int k = 0; k < idx; k += 2)
        {
            f[k] += f[k ^ 1];
            f[k ^ 1] = 0;
        }
        res = min(res, dinic());
    }
printf("%d\n", res);

3.3.1 为什么要枚举所有 $(i,j)$？

• 根据图的点连通度公式，最小点割 = 对所有顶点对最小割的最小值。
• 枚举顺序上，只要 $(i, j)$ 遍历完所有 $i<j$ 即可。

3.3.2 流量重置技巧

• for (int k = 0; k < idx; k += 2)：
  • f[k] += f[k ^ 1]; f[k ^ 1] = 0;
  • 其中 k ^ 1 就是与 k 相对的反向边。
• 因为在一次最大流计算完后，网络中的 f[] 值都发生了改变（部分容量被用掉，部分放在反向边中），如果想在同一张网络继续对新的 $(S, T)$ 再做一次最大流，我们需要把整张网络恢复到未流动时的初始容量状态。
• 但是为了不重新建图、也不用备份大数组，就采用了这个巧妙的**“流量回退”**做法。对每对正反边 $(k, k^1)$：
  • 把正向边的剩余容量 f[k] 加上反向边 f[k^1]（表示把原来已经流过去的都退回去了），
  • 再把反向边的容量 f[k^1] 置 0。
• 于是就实现了在同一个 h[], e[], ne[] 结构下“重置容量”的目的。

3.4 为什么返回 res = n 时表示不可能割开

如果最小割都在所有 $(i, j)$ 对上大于或等于 $n$，说明你至少要割掉 $n$ 条容量1的边；换句话说你需要删除所有点才能断开图。这是极端情况下的回答。

---

4. 算法正确性的内在机理

综合上文，我们可以从更高层次来理解：

1. 点割的本质

   • 删除一个点，就相当于把该点“in-out”之间的容量1边割掉。
   • 这样就失去了经过这个点的所有“in → out → 其他节点”的路径。
   • 若想把两个特殊顶点 $(s,t)$ 分到不同连通分量中，割集合只能由若干个这样的容量1边组成。

2. 对所有 $(s,t)$ 求最小割，取其最小值

   • 点连通度是把任意两个顶点分到不同分量中时所需的最少点数。
   • 如果对某对 $(s, t)$ 的最小割代价特别低，那么整张图能被较小的点集割断。

3. 返回 $n$ 的情况

   • 若图“非常连通”，比如完全图 $K_n$，你要想拆分成不连通的两部分，通常需要把所有点之一方都删光才行——这就导致最小割= $n-1$ 或更大的情况(在一些约定下也可能是 $n$ 这个值，根据题意最终取整张图的点数作为“实在割不断”的标志)。
   • 代码里统一用 res = n 作为极限值，“如果所有双点间最小割都>=n，就说明要删至少n个点才能让图不连通，那就是把全体点都删光”。

---

5. 算法复杂度与可行性

1. 节点规模 $n \leq 50$，枚举所有对 $(i,j)$ 需要 $\mathcal{O}(n^2)$ 次。
2. 每次 Dinic 最坏复杂度为 $\mathcal{O}(E\sqrt{V})$（或者 $\mathcal{O}(\min\{V^{2/3},E^{1/2}\}E)$ 的各种不同分析），在本题里 $V\approx 2n \leq 100$，$E$ 在最坏情况下也就在几千级别(考虑拆点后、加上多重无向边等)。
3. 整体在 $n=50$ 范围内运算是可行的。

---

6. 小结与深层洞察

1. 本质：

   • 我们要找的是最小点割，这与最小边割不同。最小边割通常只需直接跑一次最大流最小割即可（配合选定源汇），但点割需要拆点。
   • 之所以要对所有 $(i,j)$ 做最小割并取最小值，是因为点连通度定义就是「使图不连通」等价于「至少有一对顶点被分到不同分量」。要让图中至少有一对顶点彼此无法相互可达，就得看割开那对顶点的最小切割花费。

2. 技术关键：

   • 拆点：把一个点分成 in/out 两部分，用容量1的边连接，以此把“删除顶点”映射成“切断一条容量1的边”。
   • 对所有 (s, t) 组合跑最小割：这与边连通度只需要跑一次（或多次特定策略）不同，点连通度通常需要遍历所有顶点对。
   • 流量重置技巧：不必重复建图，而是通过把反向边的剩余容量加回原边来实现容量重置，节省实现复杂度和运行时间。

3. 更高阶思考：

   • 在实际运用中，如果 $n$ 大很多，这种 $\mathcal{O}(n^2)$ 次最大流会比较昂贵。大规模问题往往需要采用更高效或近似的算法。但在题目规定的 $n \le 50$ 范围内，这是够用且易于实现的经典做法。
   • 还有一些求点连通度的更高阶算法（如基于最大流的割边合并技巧、碰撞法等），但它们实现更复杂。以题意和规模而言，“拆点+对所有点对跑Dinic”是最直接稳健的方法。

---

7. 结语

• 核心思路：通过点拆分将「点容量=1」转化为「in→out」的边容量=1，再把原无向边转为无限容量；然后利用最大流最小割来求出对任意 $(s, t)$ 的最小点割，遍历所有顶点对，取最小值即可得到图的点连通度。
• 本质洞见：** 点割与最小割之间的差异**在于对点的处理，拆点是关键。这个过程完美地将“删除点”映射成“切断容量为1的边”。
• 实现亮点：代码中通过「流量回退」来重复利用同一套邻接表结构，从而减少重复建图的开销。

以上便是对该题及其代码最核心、本质且尽可能深入的分析。希望能帮助你彻底掌握「最小点割」及其与「最大流-最小割算法」相结合的技巧。