BZOJ-2530: [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]

考虑假设两个点没有连边，那么说明这两个点都不在一个团里。把这两个点都删除。最后肯定能够剩一个n/3的团。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,cnt;
bool map[3100][3100],v[3100];
int main()
{
    scanf("%d%d",&n,&m);
    int x,y;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        map[x][y]=1; map[y][x]=1;
    }
    for(int i=1;i<=n;i++)
    {
        if(!v[i])
        {
            for(int j=i+1;j<=n;j++)
                if(cnt<n/3&&!v[i]&&!v[j]&&!map[i][j])
                {
                    v[i]=1,v[j]=1;
                    cnt++;
                    break;
                }
        }
        if(cnt==n/3) break;
    }
    cnt=0;
    for(int i=1;i<=n&&cnt<n/3;i++)
        if(!v[i])
        {
            cnt++;
            printf("%d%c",i,(cnt==n/3)?'\n':' ');
        }
    return 0;
}