图论中团问题的贪心算法解析与实现

1. 题目解析与算法思路

这道题目来自波兰信息学奥林匹克竞赛（POI 2011），属于图论中的团（clique）问题变种。题目要求我们在一个图中找到一个大小为n/3的团，即一组两两互相认识的顶点集合。

1.1 题目核心理解

题目给出了几个关键信息：

1. 朋友数量n能被3整除
2. 图中存在一个大小为2n/3的团（即2n/3个顶点两两相连）
3. 需要找出任意一个大小为n/3的团

这个问题的特殊之处在于题目保证了解的存在性，这为我们设计算法提供了重要线索。由于大团的存在，我们可以利用这个性质设计出比一般团问题更高效的解法。

1.2 算法选择思路

对于一般的团问题，寻找最大团是NP难问题。但本题的特殊条件让我们可以采用贪心策略：

1. 初始化所有顶点为未标记状态
2. 遍历所有顶点对(i,j)，如果i和j不相连且都未被标记，则标记这对顶点
3. 最终未被标记的顶点就构成一个合法解

这个算法的正确性基于以下观察：在原图中存在一个大小为2n/3的团，其中任意两个顶点都是相连的。因此，我们最多只能标记n/3对不相连的顶点（因为最多有n/3个不在大团中的顶点），所以最终至少会剩下n/3个未标记的顶点，这些顶点两两相连。

2. 代码实现详解

2.1 数据结构设计

cpp复制const int N=3010;
int n,m,mapp[N][N],vis[N],cnt=0;

• mapp[N][N]：邻接矩阵存储图结构，mapp[i][j]=1表示顶点i和j相连
• vis[N]：标记数组，vis[i]=1表示顶点i被排除在解集外
• cnt：计数器，记录已找到的解的数量

2.2 输入处理

cpp复制n=read(),m=read();
for(int i=1;i<=m;i++){
    int a,b;
    a=read(),b=read();
    mapp[a][b]=mapp[b][a]=1;
}

这里使用了快速读取函数read()来处理大量输入数据，这在算法竞赛中很常见，可以显著提高输入速度。

2.3 核心算法实现

cpp复制for(int i=1;i<=n;i++){
    if(vis[i]) continue;