BZOJ 1098 [POI2007] 办公楼 biu


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1098

题意:给一个无向图,把点分组,不同的组间的点必须有边相连,求最大组数和每组点数。


显然答案即是补图的连通块数,如果有补图的话,很好做,不过点数太多了,补图建不起来,怎么办呢。

考虑我们要做什么:直接 bfs 整个图即可,束缚复杂度的瓶颈在于每次找到没有被访问过的点更新答案,由于没有图,这一步做不到\(O(1)\),如果\(O(n)\) 就死定了。

考虑到每个点只需被访问一次,把所有点用链表串起来,每次遍历整个链表,没被标记过的就丢到队列里去。

考虑时间复杂度:每个节点只会被遍历到一次,遍历到就从链表里删去,每次是\(O(1)\) 的,这一步是\(O(n)\) 的。

考虑每条边对时间复杂度的贡献,每条边最多会被两个端点各访问一次,这一步是\(O(m)\) 的,所以整个复杂度是\(O(n+m)\) 的。

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 1098 [POI2007] 办公楼 biu


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , ,