---

题意翻译

给定一个 $n$ 个节点的无向图，保证图是 $k$-退化图（即任意导出子图中存在度数 $<k$ 的节点）。
求该图的 最大团（完全子图）大小。

数据范围：$n \le 5\times 10^4$，$1 \le k \le 10$。

---

核心性质

$k$-退化图 的性质：

• 存在一个顶点排序 $v_1, v_2, \dots, v_n$，使得每个 $v_i$ 在 $\{v_i, v_{i+1}, \dots, v_n\}$ 中的度数 $\le k$。
• 这个排序可以通过反复删除当前度数最小的节点得到。

---

算法思路

1. 求退化序（贪心）

用最小堆（按度数）不断取出当前度数最小的节点，加入序列末尾。
复杂度：$O(n \log n)$。

2. 在退化序上搜索最大团

按退化序的逆序处理节点（即从最后一个节点开始往前）。

对于节点 $u$，设它的邻居集合 $N(u)$ 中在退化序里排在它后面的节点集合为 $S$。
因为 $|S| \le k$，所以 $S$ 的大小很小。

我们可以在 $S \cup \{u\}$ 中搜索最大团：

• 用位运算或回溯法枚举 $S$ 的所有子集，检查是否构成团。
• 由于 $|S| \le k \le 10$，子集最多 $2^{k}$ 个，可接受。

---

公式表达

设：

• $deg(v)$ 表示节点 $v$ 的度数
• $N(v)$ 表示 $v$ 的邻居集合
• $\pi$ 是退化序，$\pi(i)$ 表示第 $i$ 个节点

退化序性质：

$$\forall i,\ |\{ \pi(j) \in N(\pi(i)) \mid j > i \}| \le k $$

最大团搜索： 对每个 $u$，令

$$S = \{ v \in N(u) \mid \text{$v$ 在退化序中在 $u$ 之后} \} $$

则包含 $u$ 的团必在 $\{u\} \cup T$ 中，其中 $T \subseteq S$ 且 $T$ 是团。

---

伪代码

1. 计算退化序 order[] （最小度贪心）
2. ans = 1
3. 对于 i = n-1 到 0:
       u = order[i]
       S = { v | v 在 N(u) 中且在 order 中位置 > i }
       枚举 S 的所有子集 T:
           如果 T 是团 且 {u} ∪ T 是团:
               ans = max(ans, |T|+1)
4. 输出 ans

---

复杂度分析

• 退化序构建：$O(n \log n)$
• 最大团搜索：每个节点最多有 $k$ 个后继邻居，枚举子集 $O(2^k)$，检查团 $O(k^2)$
  总复杂度 $O(n \cdot 2^k \cdot k^2)$，在 $k \le 10$ 时可接受。

---

示例

样例 1：

5 3
2 1 2
3 0 2 3
3 0 1 4
2 1 4
2 2 3

退化序可能为 [4,3,0,1,2] 等，搜索得最大团大小为 3。

---

总结

利用 $k$-退化图 的优良性质，通过 贪心求退化序 + 逆序搜索小规模子集，将 NP 难的最大团问题在特殊图上高效解决。