【BZOJ2530】[Poi2011]Party
Description
给定一张N（保证N是3的倍数）个节点M条边的图，并且保证该图存在一个大小至少为2N/3的团。
请输出该图的任意一个大小为N/3的团。 一个团的定义为节点的一个子集，该子集中的点两两有直接连边。 输入： 第一行是两个整数N,M。 接下来有M行，每行两个整数A,B，表示A和B有连边。保证无重边。 输出： N/3个整数，表示你找到的团。
数据范围：
3<=N<=3000,[3/2 n(2/3 n -1)]/2<=M<=[n(n-1)/2]
Sample Input
6 10
2 5
1 4
1 5
2 4
1 3
4 5
4 6
3 5
3 4
3 6
2 5
1 4
1 5
2 4
1 3
4 5
4 6
3 5
3 4
3 6
Sample Output
2 4
题解：首先我们知道，在原图中找团，就是在补图中找出一些点使得两两之间不直接相连。
所以我的做法是：先搞出原图的补图，然后每次贪心选取（补图中）度数较少的点，将所有与它直接相连的点去掉，直到找出n/3个点。
结果一交上去就A了，看题解发现根本没必要贪心，随机选点就行了。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int n,m;
int A[3010][3010],d[3010],vis[3010];
int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
int main()
{
int i,j,a,b;
n=rd(),m=rd();
for(i=1;i<=n;i++) for(d[i]=n-1,j=1;j<=i;j++) A[i][j]=A[j][i]=1;
for(i=1;i<=m;i++) a=rd(),b=rd(),A[a][b]=A[b][a]=0,d[a]--,d[b]--;
d[0]=n;
for(i=1;i<=n/3;i++)
{
for(a=0,j=1;j<=n;j++) if(!vis[j]&&d[j]<d[a]) a=j;
vis[a]=1;
if(i>1) printf(" ");
printf("%d",a);
for(j=1;j<=n;j++) if(A[a][j]) vis[j]=1;
}
return 0;
}