题目

有一个 \(3n\) 个点的无向图，保证有一个大小为 \(2n\) 的团，输出一个大小为 \(n\) 的团

分析

每次选择两个不相连的点删掉，那么剩下的 \(n\) 个点一定是团，

因为每次至少有一个不在大小为 \(2n\) 的团中的点被删除，所以剩下的点一定在团中。

但是只是最多删除 \(n\) 次，所以输出完 \(n\) 个点后及时退出。

代码

#include <cstdio>
#include <cctype>
using namespace std;
const int N=3011; int n,ans;
bool kick[N],a[N][N];
int iut(){
	int ans=0; char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=ans*10+c-48,c=getchar();
	return ans; 
}
int main(){
	n=iut();
	for (int T=iut();T;--T){
		int x=iut(),y=iut();
		a[x][y]=a[y][x]=1;
	}
	for (int i=1;i<=n;++i)
	if (!kick[i]){
		for (int j=i+1;j<=n;++j)
		if (!kick[j]&&!a[i][j]){
			kick[i]=kick[j]=1;
			break;
		}
	}
	for (int i=1;i<=n;++i)
	if (!kick[i]){
		printf("%d ",i);
		if (++ans==n/3) break;
	}
	return 0;
}