1. 问题重述

我们有：

• $n$ 个学生，编号 $0$ 到 $n-1$
• 朋友关系是双向的，构成无向图 $G = (V, E)$
• 要把 $V$ 划分成若干组 $S_1, S_2, \dots, S_G$，满足：
  1. $1 \le |S_k| \le p$ 对每个组 $S_k$
  2. 对每个组 $S_k$，定义 跨组朋友对 数量：$$q_k = \big|\{ (u,v) \in E \mid u \in S_k, v \notin S_k \} \big| $$要求 $q_k \le q$。

问是否存在这样的划分，若存在则输出一个方案。

---

2. 关键观察

2.1 跨组边数的公式

设 $d_S(u)$ 表示顶点 $u$ 在组 $S$ 内的度数（与组内朋友的数量）。

那么 $u$ 的跨组边数 $= \deg(u) - d_S(u)$。

整个组 $S$ 的跨组边数：

$$q_S = \sum_{u \in S} \big[ \deg(u) - d_S(u) \big]$$

注意每条跨组边在组 $S$ 这一侧只算一次，所以这个公式正确。

因为 $\sum_{u \in S} d_S(u) = 2 \cdot |E(S)|$，其中 $E(S)$ 是 $S$ 内部的边集，所以：

$$q_S = \sum_{u \in S} \deg(u) - 2 \cdot |E(S)|$$

---

2.2 合法组的条件

一个顶点子集 $S$ 能作为一组，当且仅当：

1. $1 \le |S| \le p$
2. $q_S \le q$

因为 $p+q \le 15$，可能的合法组不会太多。

---

3. 算法思路

3.1 局部性原理

重要性质：任何合法组 $S$ 的 外部邻居集合 $\partial S = \{ v \notin S \mid \exists u \in S, (u,v) \in E \}$ 的大小不超过 $q$，因为跨组边数 $\le q$，且不同组内顶点可能连接到同一个外部顶点，所以外部邻居数 $\le q$。

于是：

$$|S \cup \partial S| \le p + q \le 15$$

这意味着：每个合法组及其直接邻居的总顶点数 $\le 15$。

---

3.2 枚举合法组

对每个顶点 $v$，考虑它的 $(p+q)$-邻域：即 $v$ 及其距离 $\le 1$ 的顶点中，大小不超过 $p+q$ 的集合。

实际上，我们枚举所有大小 $\le p$ 且包含 $v$ 的集合 $C \subseteq N[v]$（$N[v]$ 是 $v$ 的闭邻域），检查 $C$ 是否是一个合法组：

• 计算 $|C| \le p$
• 计算 $q_C = \sum_{u \in C} \deg(u) - 2 \cdot |E(C)| \le q$

收集所有合法组存入列表 $\mathcal{L}$。

---

3.3 动态规划

我们按顶点编号 $0 \dots n-1$ 进行覆盖型 DP。

设 $f[i]$ 表示覆盖顶点 $\{0,1,\dots,i\}$ 所需的最少组数（$f[-1] = 0$）。

转移：对于每个合法组 $S$，设它包含的最大编号顶点是 $r$，最小编号顶点是 $l$，则：

$$f[r] = \min\big( f[r],\; f[l-1] + 1 \big)$$

记录转移来源用于回溯。

初始 $f[i] = \infty$，$f[-1] = 0$。

最终若 $f[n-1] < \infty$，则存在划分，组数为 $f[n-1]$。

---

3.4 回溯构造方案

从 $r = n-1$ 开始，根据 DP 转移记录，找到最后一组 $S$，然后跳到 $l-1$ 继续回溯，得到所有组。

---

4. 复杂度分析

• 枚举合法组：对每个顶点 $v$，枚举 $N[v]$ 的大小 $\le p$ 的子集，$\binom{|N[v]|}{\le p}$，在 $p \le 15$ 时可接受。
• DP 阶段：$O(n \cdot |\mathcal{L}|)$，$|\mathcal{L}| \le n \cdot \binom{p+q}{p}$ 量级。

---

5. 总结公式

1. 合法组条件：$$|S| \le p, \quad \sum_{u \in S} \deg(u) - 2|E(S)| \le q $$
2. 局部性原理：$$|S \cup \partial S| \le p + q$$
3. DP 转移：$$f[r] = \min_{S \ni r,\, S \text{合法}} \{ f[\min(S)-1] + 1 \} $$

这样我们就能在 $p+q \le 15$ 的约束下高效求解。