BZOJ 1098 [POI2007] 办公楼 biu

发布于 2017-10-26  206 次阅读


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

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


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

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

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

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

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

 


一个非常弱的准退役OIER