\(\\\)
给定一张 \(N\ (\ N\equiv 0\pmod{3}\ )\) 个节点,，\(M\)条边的图，并且保证该图存在一个大小至少为\(\frac{2}{3}N\)的团，以包含节点编号的形式输出该图的任意一个大小为\(\frac N 3\)的团。
- \(N\in [3,3\times 10^3]\)，\(M\in [\frac{\frac{2}{3}N\times (\frac{2}{3}N-1)}{2},\frac{N(N-1)}{2}]\)
\(\\\)
\(Solution\)
脑洞题。反图贪心的做法是可行的，这里写一个
不知道神仙出题人怎么想的更简单的做法。注意到图中最大团大小\(\ge\frac{2}{3}N\)，也就是说不在团内的点数\(\le\frac{N}{3}\)，注意到属于同一个团的两个点一定满足两点有连边，换句话说，没有边相连的点对一定不属于同一个团。
而不属于最大团的点最多只有\(\frac{N}{3}\)个，所以枚举到的没有连边的点对最多只有这么多个（枚举到的点对直接除掉，不再用于判断其他点），枚举到的点最多只有\(\frac{2}{3}N\)个。去掉这些被枚举到的点，剩下的点最少也有\(\frac{N}{3}\)个，足够构成答案。
\(\\\)
\(Code\)
#include#include #include #include #include #include #include #define N 3010#define R register#define gc getcharusing namespace std; int n,m;bool edge[N][N],v[N]; inline int rd(){ int x=0; bool f=0; char c=gc(); while(!isdigit(c)){if(c=='-')f=1;c=gc();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();} return f?-x:x;} int main(){ n=rd(); m=rd(); for(R int i=1,u,v;i<=m;++i){ u=rd(); v=rd(); edge[u][v]=edge[v][u]=1; } for(R int i=1;i<=n;++i) if(!v[i]){ for(R int j=i+1;j<=n;++j) if(!v[j]&&!edge[i][j]){v[i]=v[j]=1;break;} } for(R int i=1,cnt=0;i<=n;++i) if(!v[i]){printf("%d ",i);if(++cnt==n/3)break;} return 0;}