题意：给出一个图（N个点，M条边），让你把此图分成尽可能多的集合，满足任意不在同一集合的点之间都有边相连。
考虑对于原图：若x,y有连边，则x,y不一定不在同一个集合。
若x,y无连边，则通过题意，x,y一定在同一个集合。
故我们建出原图的补图（全集为完全图），这样就变成了找补图里的联通块个数。
怎样建图？首先O(n^2)暴力建边肯定TLE，因此我们考虑维护集合S，每次扩展一个未加入补图联通块的点x进行BFS，从集合S中选出当前点x扩展不到的点进行入队，扩展到的点还原回S，这样便不用建图也可以找出联通块。
code:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int N=100010;
const int M=2000010;
vector<int>S;
vector<int>g[N];
vector<int>ans;
bool vis[N],h[N];
int n,m;
int bfs(int s)
{
int tot=0;
queue<int>q;
q.push(s);
h[s]=1;//s被访问
while(q.size())
{
int u=q.front();q.pop();
vis[u]=1;tot++;//联通块大小+1
for(int i=0;i<g[u].size();i++)h[g[u][i]]=1;//标记访问到的点
vector<int>tmp=S;S.clear();
for(int i=0;i<tmp.size();i++)
{
if(h[tmp[i]])S.push_back(tmp[i]);//被访问的点不被拿出拓展其他点
else q.push(tmp[i]);//不被访问说明没有连边（即补图有边）入队
}
for(int i=0;i<g[u].size();i++)
h[g[u][i]]=0;//标记撤销
}return tot;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
for(int i=1;i<=n;i++)S.push_back(i);//未扩展的节点
for(int i=1;i<=n;i++)
if(!vis[i])ans.push_back(bfs(i));//bfs返回补图联通快大小
sort(ans.begin(),ans.end());
cout<<ans.size()<<endl;
for(int i=0;i<ans.size();i++)
cout<<ans[i]<<" ";
}
原文：https://www.cnblogs.com/THRANDUil/p/11279893.html