图论经典问题：完全子图(Clique)的算法设计与实现

markdown复制## 1. 题目背景与核心挑战解析

P3524 [POI 2011] IMP-Party是信息学奥林匹克竞赛中一道经典的图论题目，考察选手对完全子图（clique）问题的理解和算法设计能力。题目给定一个无向图，要求找出图中至少包含⌈n/3⌉个顶点的完全子图（即这些顶点两两之间都有边相连）。这类问题在实际应用中涉及社交网络分析、蛋白质相互作用网络研究等领域。

这道题的难点在于如何在多项式时间内解决一个本质上是NP难的问题。题目给出的特殊条件是"输入保证存在这样一个团"，这为设计确定性算法提供了突破口。我最初接触此题时，尝试用暴力枚举法显然不现实（时间复杂度O(2^n)），后来发现可以利用图论中补图的性质和贪心策略来巧妙解决。

## 2. 算法设计与数学证明

### 2.1 关键思路：补图独立集转化

这道题的精妙之处在于将原问题转化为其补图的问题。对于原图G，构造其补图G'（两个顶点在G'中有边当且仅当它们在G中没有边）。此时原问题等价于在G'中找到一个不超过2n/3个顶点的独立集（即这些顶点两两之间没有边）。

证明过程：
1. 设所求团大小为k，则在补图中对应的顶点集是一个独立集
2. 根据题意k ≥ ⌈n/3⌉，所以独立集大小 ≤ n - ⌈n/3⌉ ≤ 2n/3
3. 题目保证解存在，因此补图中必存在这样的独立集

### 2.2 确定性算法步骤

基于上述观察，可以设计如下算法：

1. 初始化候选集S包含所有顶点
2. 当|S| > 2n/3时重复：
   a. 在S中任选两个不相邻的顶点u,v（在补图中相邻）
   b. 从S中删除所有与u或v相邻的顶点（在补图中的邻居）
3. 最终剩下的S即为补图中的独立集，其补集就是原图的团

这个算法的时间复杂度是O(n^2)，因为每次迭代至少减少1个顶点，每次操作需要O(n)时间检查邻接关系。

## 3. C++实现详解

### 3.1 数据结构设计

使用邻接矩阵存储图结构更便于快速查询任意两点间的连接情况：

```cpp
const int MAXN = 3000;
bool graph[MAXN][MAXN];
bool inSet[MAXN]; // 标记顶点是否在当前集合中

3.2 核心算法实现

cpp复制void findParty(int