题解：AT_agc067_a [AGC067A] Big Clique Everywhere

· · 题解

给你一个 n 个点 m 条边的简单无向图 G，你需要判定是否 G 中所有点导出子图 X 都存在点数不少于一半的完全图 Y。

如果 G 中所有点导出子图 X 都存在点数不少于一半的完全图 Y，那么把任意一个点导出子图变成它的补图，原本的属于完全图上的点之间两两没有边，也就是这些点构成一个独立集。从而， G 的补图中所有点导出子图 X 都存在点数不少于一半的的独立集 Y。

对 G 的补图进行研究，如果存在奇环，那么取 X 为这个奇环，容易发现最大独立集 Y 有 2|Y|\le |X|-1，矛盾。从而 G 的补图中没有奇环，也就是 G 的补图是二分图。

另一个方面，如果 G 的补图是二分图，我们不妨将 G 中的点染成黑色和白色，使得每条边的两个端点一黑一白，那么对于任意的 X，如果白点个数大于等于一半，则取 Y 为 X 中所有白点；白点个数小于一半，那么黑点个数一定大于一半，从而可以取 Y 为 X 中所有黑点。综上，G 的补图是二分图时，G 一定满足条件。

所以问题转化为： - 如果 $n>\sqrt{4m+1}+1$，输出 `NO` - 否则 - 如果 $G$ 的补图是二分图，输出 `YES` - 否则输出 `NO`。 ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; const int _=2009; int a[_*_],b[_*_],c[_],d[_][_],m,n,T; void work(){ queue<int>q; for(int i=1;i<=n;i++) if(!c[i]){ c[i]=1;q.push(i); while(!q.empty()){ int x=q.front();q.pop(); for(int i=1;i<=n;i++) if(d[x][i]){ if(!c[i])c[i]=3-c[x],q.push(i); else if(c[i]==c[x]){ cout<<"NO\n"; return; } } } } cout<<"YES\n"; } int main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>T; while(T--){ cin>>n>>m; for(int i=1;i<=m;i++)cin>>a[i]>>b[i]; if(n>sqrt(4*m+1)+3)cout<<"NO\n"; else{ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++)d[i][j]=1; c[i]=d[i][i]=0; } for(int i=1;i<=m;i++)d[a[i]][b[i]]=d[b[i]][a[i]]=0; work(); } } return 0; } ``` 如果把题目中的“团”变成“联通块”，可以转化为 $G$ 的补图中没有三角形。