「BZOJ1098」[POI2007] 办公楼biu

2014年10月3日5,4570

Description

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

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

3
1 2 4

HINT

FGD可以将职员4安排进一号办公楼,职员5和职员7安排进2号办公楼,其他人进3号办公楼。

题解

求补图的连通块个数。。。

机智的使用链表+dfs。。。。

然后T了

机智地改成bfs。。。

dfs(超时。。。)

bfs。。。

 

avatar
  Subscribe  
提醒