bzoj1098 办公楼-白红宇

bzoj1098 办公楼

阅读量：6815 次

发布时间：2019-06-26

本文共 1365 字，大约阅读时间需要 4 分钟。

Description

　　FGD开办了一家电话公司。他雇用了N个职员，给了每个职员一部手机。每个职员的手机里都存储有一些同事的

电话号码。由于FGD的公司规模不断扩大，旧的办公楼已经显得十分狭窄，FGD决定将公司迁至一些新的办公楼。FG

D希望职员被安置在尽量多的办公楼当中，这样对于每个职员来说都会有一个相对更好的工作环境。但是，为了联

系方便起见，如果两个职员被安置在两个不同的办公楼之内，他们必须拥有彼此的电话号码。

Input

　　第一行包含两个整数N（2<=N<=100000）和M（1<=M<=2000000）。职员被依次编号为1,2,……,N.以下M行，每

行包含两个正数A和B(1<=A

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

1 2 4

Solution

比较显然的是，这是求一个稀疏图的反图的联通块数量

想了很久，问了问ysy

woc！

因为稀疏图非常稀疏，所以每次暴力去做就过了！！

就过了！！

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #include
                
                 #define il inline#define re registerusing namespace std;const int N=100009;int n,next[N],last[N],vis[N],fin[N],ans,m;queue
                 
                   q;vector
                  
                    g[N];il void del(int i){ last[next[i]]=last[i]; next[last[i]]=next[i];}il int read(){ int hs=0;char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)){ hs=(hs<<3)+(hs<<1)+c-'0'; c=getchar(); } return hs;}il void work(int S){ ans++;q.push(S);vis[S]=true; while(!q.empty()){ int h=q.front();q.pop();fin[ans]++; for(int i=next[0],k=0;i<=n;i=next[i]){ while(k