• Source 
    1. /**************************************************************
    2.     Problem: 1098
    3.     User: zrts
    4.     Language: C++
    5.     Result: Accepted
    6.     Time:11688 ms
    7.     Memory:34108 kb
    8. ****************************************************************/
    9.  
    10. #include<cstdio>
    11. #include<cstring>
    12. #include<algorithm>
    13. //by zrt
    14. //problem:
    15. using namespace std;
    16. typedef long long ll;
    17. const double eps(1e-10);
    18. int n,m;
    19. int H[100005],X[4000005],P[4000005],tot;
    20. int q[100005],h,t;
    21. int siz[100005],cnt;
    22. inline void add(int x,int y){
    23.     P[++tot]=y;X[tot]=H[x];H[x]=tot;
    24. }
    25. int pre[100005],nxt[100005];// nxt[0] head;
    26. bool now[100005];
    27. int main(){
    28.     #ifdef LOCAL
    29.     freopen("in.txt","r",stdin);
    30.     freopen("out.txt","w",stdout);
    31.     #endif
    32.     scanf("%d%d",&n,&m);
    33.     for(int i=0,x,y;i<m;i++){
    34.         scanf("%d%d",&x,&y);
    35.         add(x,y);add(y,x);
    36.     }
    37.     for(int i=0;i<n;i++) nxt[i]=i+1;
    38.     nxt[n]=0;
    39.     for(int i=1;i<=n;i++) pre[i]=i-1;
    40.     int k;
    41.     while(nxt[0]){
    42.         {
    43.             cnt++;h=t=0;
    44.             q[t++]=nxt[0];
    45.             nxt[0]=nxt[nxt[0]];
    46.             pre[nxt[0]]=0;
    47.             while(h!=t){
    48.                 k=q[h++];
    49.                 siz[cnt]++;
    50.                 memset(now,0,sizeof now);
    51.                 for(int i=H[k];i;i=X[i]){
    52.                     now[P[i]]=1;
    53.                 }
    54.                 for(int i=nxt[0];i;i=nxt[i]){
    55.                     if(!now[i]){
    56.                         q[t++]=i;
    57.                         nxt[pre[i]]=nxt[i];
    58.                         pre[nxt[i]]=pre[i];
    59.                     }
    60.                 }
    61.             }
    62.         }
    63.     }
    64.     sort(siz+1,siz+cnt+1);
    65.     printf("%d\n",cnt);
    66.     for(int i=1;i<=cnt;i++) printf("%d ",siz[i]);
    67.     return 0;
    68. }