首页 > 其他 > 详细

Codeforces 920E(补图BFS)

时间:2018-02-03 22:41:45      阅读:269      评论:0      收藏:0      [点我收藏+]

题意:

  n(n<=200000)个点的完全图删去了m(m<=200000)条边,求剩下图的连通分量。

分析:

  将未访问过的点用一个链表串起来

  仍旧进行BFS,每次BFS扩展一个点u的时候,暴力去for链表,如果发现有与u相连的点则该点入队且从链表删除

  直至链表为空

  我们来分析一下这个的复杂度,首先明显每个点只会删除一次,O(n)

  但是一个点会被for很多次,我们发现被for很多次是在原图有边的情况,所以是O(2*m)

  总的复杂度O(n+m)

  具体在实现过程中,要判断两点是否右边,所以要用一个set,复杂度多个log

Codeforces 920E(补图BFS)

原文:https://www.cnblogs.com/wmrv587/p/8410834.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!