Michael_Bryant最喜欢的G(al)G(ame)

那些悲伤,那些寂寞,那些几乎让自己放弃生活的希望的痛苦的回忆,绝对绝对不要将它们忘记。

Michael_Bryant最喜欢的番剧

抱歉⋯我已经绝对不可能再获得幸福了,因为⋯我发现⋯ 其实我⋯ 早就已经被幸福包围了

Michael_Bryant正在看的番剧

死亡一点也不温柔,只有无尽的黑暗和孤独。 就算联系得再紧密,人也是孤独的。

bzoj 1098: [POI2007]办公楼biu

题目链接

传送门

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

想说的话

这个题是komqaq神犇给我们讲的
然后当时讲的时候我们口胡了很多的东西
当时我记得我提到过并查集的想法
然而被他D了
然后发现正解其实是链表
但是我不会链表你说这气不气人
于是乎
我选择并查集

题解

这个题解自然很好想了
题目大意:给定一张无向图,一个点集能分成两部分当且仅当这两部分的每一对点之间都有边,求最多能分成多少部分以及每部分的大小
这实际上就是在求反图的联通块个数以及每个联通块大小
但是反图太大,不能直接做
因此我们枚举每个点,从这个点开始DFS
这样做是O(n^2)的,但是我们可以利用并查集来减少枚举的复杂度
一个点x如果访问过,就在并查集中连向x+1 这样做的好处是枚举的时候可以直接找到下一个没有访问过的点
其实链表也是这么做
链表就是bfs的思想
每次找到不联通的点就删除
链表那个O(N+M)我觉得很好想
毕竟每个点会被删除一次然后每条边会走一次嘛
所以下面我重点说说并查集时间复杂度证明

时间复杂度证明

我们用一个函数来表示
定义函数Φ为当前未访问过的点数和未访问过的边数之和
初始Φ=n+m,显然任意时刻Φ>=0
每枚举到一个点y,如果x没有向y的边,那么未访问过的点数-1,故Φ会-1
如果x有向y的边,那么未访问过的边数-1,故Φ会-1
因此最终DFS的复杂度为O(n+m)
然后就随便搞了
所以说并查集的优化跟链表的复杂度是类似的

纪念意义

这是我史上第一次用了vector存图

代码

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注

隐藏