POI2011 R3」聚会 Party 题解

题目解析

Byteasar 有 $n$ 个朋友（$n$ 是 $3$ 的倍数），这些朋友之间有一些互相认识的关系。已知存在一个大小为 $\frac{2}{3}n$ 的团（完全子图），要求我们找出一个大小为 $\frac{n}{3}$ 的团。

关键信息：

存在一个大小为 $\frac{2}{3}n$ 的团

要求输出一个大小为 $\frac{n}{3}$ 的团

$n \le 3000$

算法思路

核心观察 补图性质：如果两个人在原图中不互相认识，那么他们在补图中有一条边

团与独立集：原图中的团对应补图中的独立集（没有边连接的顶点集）

关键结论 ：补图中最大独立集至少为 $\frac{n}{3}$

贪心算法 我们可以使用简单的贪心策略在补图中寻找独立集：

构建补图：根据原图的边关系，找出所有不相识的朋友对

贪心选择：

初始化一个空集合 $S$

对于每个顶点 $v$，如果 $v$ 与 $S$ 中的所有顶点都不相邻（在补图中），则将 $v$ 加入 $S$

否则跳过 $v$

保证性质：由于原图存在大小为 $\frac{2}{3}n$ 的团，在补图中对应的顶点形成大小为 $\frac{n}{3}$ 的独立集，所以贪心算法一定能找到足够大的独立集

更简单的实现 实际上，我们可以直接在原图上操作：

初始化集合 $S = {1, 2, \ldots, n}$

不断删除不相识的对：

在 $S$ 中寻找两个不相识的顶点 $u$ 和 $v$

将 $u$ 和 $v$ 都从 $S$ 中删除

终止条件：当 $|S| \ge \frac{n}{3}$ 时停止

正确性证明：

每次删除两个不相识的顶点

由于原图存在大小为 $\frac{2}{3}n$ 的团，这些顶点都互相认识

因此最多删除 $\frac{n}{3}$ 对顶点

最终剩余至少 $\frac{n}{3}$ 个顶点，且它们都互相认识

算法步骤

读入 $n, m$ 和边关系

建立邻接矩阵或邻接表存储认识关系

初始化答案集合 $S$ 包含所有顶点

不断执行：

在 $S$ 中寻找两个不相识的顶点

如果找到，将它们都从 $S$ 中移除

否则跳出循环

当 $|S| > \frac{n}{3}$ 时，可以删除任意顶点直到大小为 $\frac{n}{3}$

输出 $S$ 中的顶点

复杂度分析 时间复杂度：$O(n^3)$ 最坏情况，但对于 $n \le 3000$ 可以接受

空间复杂度：$O(n^2)$ 存储邻接矩阵

优化 可以使用位集（bitset）优化邻接矩阵存储和查找操作，将复杂度降到 $O(n^3/64)$。

算法特点

简洁性：算法思路简单，实现直接

正确性：基于图论的基本性质保证能找到解

高效性：对于 $n \le 3000$ 的数据范围可行

这种方法巧妙地利用了原图和补图的对偶关系，通过贪心删除不相识的顶点对，保证了最终集合中所有顶点都互相认识。