[文章目录]
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;
}