BZOJ1098 [POI2007]办公楼biu 链表+BFS

发布于 2017-07-10  2.51k 次阅读


[toggle hide="yes" title="题目" color=""]

题目描述

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

输入

第一行包含两个整数N(2<=N<=100000)和M(1<=M<=2000000)。职员被依次编号为1,2,……,N.以下M行,每行包含两个正数A和B(1<=A<b<=n),表示职员a和b拥有彼此的电话号码),li <= 1000

输出

包含两行。第一行包含一个数S,表示FGD最多可以将职员安置进的办公楼数。第二行包含S个从小到大排列的数,每个数后面接一个空格,表示每个办公楼里安排的职员数。

样例输入

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

样例输出

3

1 2 4

提示

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

[/toggle]

今天上午考试“最简单”的一道题,一上来很容易就想到了构建反图,然后对每个连通分量计数,搞了半天O(n^2)暴力,还以为能轻松过,后来算了一下内存,才发现162MB的内存,撑死也就算到11000,最后确实也只得了60分。

题解:

考虑优化构建反图,减少无用的枚举次数:将未分配反图中连通分量的点构成链表,初始状态下也就是所有的点,当链表非空时,每次取表头的元素入队并从链表中删去,对于队列,每次取队首元素,用当前时间戳更新所有直接相连的点,对于既属于链表、时间戳又与当前时间戳不同的元素,可以断定,该元素没有与当前队首元素直接相连,在反图中也就一定属于同一个连通分量,因此,为该元素找到了连通分量,再在链表中删去,入队继续BFS即可。

代码:

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974