[POI2011]IMP-Party

摘要

题意：一个 n 个点 m 条边的无向图 (nequiv 0(mod 3))，保证存在一个大小为 (frac{2}{3}n) 的团，要求输出一个大小为 (frac{1}{3}n) 的团.(nleq 3000).

这道题的特殊之处在于找团，而它保证有一个 (frac{2}{3}n) 大小的团，却只让我们找一个 (frac{1}{3}n) 的团. 这意味着我们在寻找的过程中可以舍弃一些点。

团中的点是两两相邻的，因此我们直接枚举判断不相邻的两个点并直接舍掉. 每个点最多被舍掉一次. 考虑这样做的正确性. 你找到的两个点一定不可能同时是 (frac{2}{3}n) 团中的点，要么一个是团中的点一个不是，要么两个都不是其中的点. 因此这个操作最多进行 (frac{1}{3}n) 次，每次取 2 个点，最后剩下的 (frac{1}{3}) 个点一定是一个团。

#include<bits/stdc++.h>
using namespace std;
const int N=3e3+5;

int n,m,e[N][N];
bool v[N];

int main(){
    ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		e[u][v]=e[v][u]=1;
	}
	for(int i=1;i<=n;i++){
        if(v[i])continue;
		for(int j=i+1;j<=n;j++)if(!v[j]&&!e[i][j]){
			v[j]=v[i]=1;break;
		}
	}
	int tot=0;
	for(int i=1;i<=n;i++){
        if(!v[i])cout<<i<<' ',++tot;
		if(tot*3==n)break;
	}
	return 0;
}