题目描述

Description

　　FGD开办了一家电话公司。他雇用了N个职员，给了每个职员一部手机。每个职员的手机里都存储有一些同事的电话号码。由于FGD的公司规模不断扩大，旧的办公楼已经显得十分狭窄，FGD决定将公司迁至一些新的办公楼。FGD希望职员被安置在尽量多的办公楼当中，这样对于每个职员来说都会有一个相对更好的工作环境。但是，为了联系方便起见，如果两个职员被安置在两个不同的办公楼之内，他们必须拥有彼此的电话号码。

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号办公楼。

题目分析

题意很明确了= = 画出样例后发现就是让你求出反图的联通块个数
但是这点数边数如此巨大 直接建图绝逼炸QAQ
以下是奇技淫巧:先把所有点用链表串起来 然后将链头元素扔进一个队列里 枚举所有这个点到不了的点 扔进队列并且从链表里删除 循环操作直到队列里没有元素 这时 我们就成功找出了反图的一个联通块 循环操作一直到链表被删完为止
大概就是用链表优化了BFS 成功get链表删除新技能
时间复杂度

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m,tot;
int pre[100100],nxt[100100];
int head[2001000],to[4001000],net[4001000];
void add(int x,int y)
{
    net[++tot]=head[x];
    head[x]=tot;
    to[tot]=y;
}
int ans[100100];
int cnt,color;
int vis[100100];
void del(int i)
{
    nxt[pre[i]]=nxt[i];
    pre[nxt[i]]=pre[i];
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
    }
    nxt[0]=1;
    for(int i=1;i<=n;i++)
        nxt[i]=i+1,pre[i]=i-1;
    pre[n+1]=n;
    while(nxt[0]!=n+1)
    {
        queue<int>q;
        cnt=0;
        q.push(nxt[0]);
        del(0);
        while(q.size())
        {
            color++;
            int x=q.front();
            q.pop();
            for(int i=head[x];i;i=net[i])
                vis[to[i]]=color;
            for(int i=nxt[0];i!=n+1;i=nxt[i])
                if(vis[i]!=color) q.push(i),cnt++,del(i);
        }
        ans[++ans[0]]=cnt;
    }
    sort(ans+1,ans+ans[0]+1);
    printf("%d\n",ans[0]);
    for(int i=1;i<=ans[0];i++) printf("%d ",ans[i]);
    return 0;
}