Description
  FGD开办了一家电话公司。他雇用了N个职员,给了每个职员一部手机。每个职员的手机里都存储有一些同事的
电话号码。由于FGD的公司规模不断扩大,旧的办公楼已经显得十分狭窄,FGD决定将公司迁至一些新的办公楼。FG
D希望职员被安置在尽量多的办公楼当中,这样对于每个职员来说都会有一个相对更好的工作环境。但是,为了联
系方便起见,如果两个职员被安置在两个不同的办公楼之内,他们必须拥有彼此的电话号码。
Input
  第一行包含两个整数N(2<=N<=100000)和M(1<=M<=2000000)。职员被依次编号为1,2,……,N.以下M行,每
行包含两个正数A和B(1<=A<b<=n),表示职员a和b拥有彼此的电话号码),li <= 1000
Output
  包含两行。第一行包含一个数S,表示FGD最多可以将职员安置进的办公楼数。第二行包含S个从小到大排列的
数,每个数后面接一个空格,表示每个办公楼里安排的职员数。
Sample Input
7 16
1 3
1 4
1 5
2 3
3 4
4 5
4 7
4 6
5 6
6 7
2 4
2 7
2 5
3 5
3 7
1 7
Sample Output
3
1 2 4
HINT
FGD可以将职员4安排进一号办公楼,职员5和职员7安排进2号办公楼,其他人进3号办公楼。

给一个图,图中没有边相连的就必须在同一栋楼里,反过来想,不就是求补图的连通块嘛,但是这题数据很大,建不了图,看了题解的骚操作,用模拟链表来优化bfs
就是先创建一个队列,把所有点都加进去,然后从链表中取出点进行bfs,标记相邻的边,这些边就不是同一个连通分量的,所以把没标记的边也就是同一个连通分量的从链表中删去,这样就达到优化的效果

代码:

#include <bits/stdc++.h>
using namespace std;
const int N=100050;
const int M=4000050;
struct Edge{
   
    int v,next;
}edge[M];
int cnt,head[N];
void init(){
   
    cnt=0;
    memset(head,-1,sizeof(head));
}
void addEdge(int u,int v){
   
    edge[cnt]=Edge{
   v,head[u]};
    head[u]=cnt++;
    edge[cnt]=Edge{
   u,head[v]};
    head[v]=cnt++;
}

int n,m,u,v;
//链表
int pre[N],nex[N];
//连通块
int ans,num[N];
//队列
int q[N];
bool flag[N];
void del(int x){
   
    nex[pre[x]]=nex[x];
    pre[nex[x]]=pre[x];
}
void bfs(int x){
   
    //模拟队列
    int hea=0,tai=1;
    q[0]=x;
    while(hea<tai){
   
        num[ans]++;
        int u=q[hea++];
        for(int i=head[u];i!=-1;i=edge[i].next){
   
            int v=edge[i].v;
            //标记一下相连的边,后边删除没连的边
            flag[v]=true;
        }
        for(int i=nex[0];i<=n;i=nex[i]){
   
            //删除链表中未标记的点并入队
            if(!flag[i]){
   
                del(i);
                q[tai++]=i;
            }
        }
        for(int i=head[u];i!=-1;i=edge[i].next){
   
            int v=edge[i].v;
            flag[v]=false;
        }
    }
}
int main(void){
   
    scanf("%d%d",&n,&m);
    init();
    while(m--){
   
        scanf("%d%d",&u,&v);
        addEdge(u,v);
    }
    //双向链表
    for(int i=0;i<=n;i++){
   
        nex[i]=i+1;
    }
    for(int i=1;i<=n+1;i++){
   
        pre[i]=i-1;
    }
    //遍历链表
    for(int i=nex[0];i<=n;i=nex[0]){
   
        //对一个链表中的点进行bfs,每次遍历与他不相邻的点
        //在补图中就是同一个连通块,所以标记这些不相邻的点并在链表中删除
        del(i);
        //连通块++
        ans++;
        bfs(i);
    }
    printf("%d\n",ans);
    sort(num+1,num+ans+1);
    for(int i=1;i<=ans;i++){
   
        printf("%d ",num[i]);
    }
    printf("\n");
    return 0;
}