补图连通性
给定稀疏图,求补图的连通块;用未访问集合做 BFS,间接遍历稠密补图,O((n+m) log n)。标签 图论 / 补图 / BFS / 问题模型
模型概述
给定一个简单无向图 ,,,且 通常较小。需要求补图 的连通块数、连通性,或每个点所属的连通块。
补图 保留全部顶点,两点之间有边当且仅当它们在 中不相邻:
补图可能有 条边,不能直接建图;但 稀疏,因此可以利用“在 中不相邻”这一条件间接遍历补图。
抽象形式
输入是 的邻接表,可以 判断一条边是否属于 。
要求输出:
- 的连通块数;或
- 每个点在 中的连通块编号;或
- 各个连通块的大小。
核心查询是:对当前点 ,找出所有尚未访问、且与 在 中不相邻的点。
框架
维护一个集合 unvisited,初始包含全部顶点。外层每次取出一个未访问点 ,连通块数加一,从 开始 BFS。
对队首 ,遍历 unvisited 中的所有 :
- 若 ,则 是补图边,把 从
unvisited删除并入队; - 若 ,则 暂时保留,等后续点发现它。
同一个点一旦被删除,就不会再被其他点重复发现。遍历时先收集本轮要删除的点,再统一删除,避免迭代器失效。
正确性
BFS 只在 时扩展,因此走过的每条边都属于补图。
若两个点在补图中连通,沿补图路径依次扩展,路径上的点都会被加入队列;反之,所有被加入队列的点都通过补图边相连。因此每个连通块恰好被外层计数一次。
复杂度
每个点最多从 unvisited 删除一次,对应 次成功发现。
每次检查 但没有删除 时, 必是 的边;由于 已经被访问并从集合中删除,这条边不会在反方向再次被检查。因此这类检查总数是 。
总检查次数 。用有序集合维护 unvisited 时,每次删除和遍历有 代价,总复杂度
空间 。
变式
- 01-MST: 边图就是给定 边图的补图;若补图有 个连通块,MST 权值为 。
- 补图 BFS / 最短路:按层扩展时同时记录距离,可以求补图上的最短路。
- 连通块大小:BFS 时统计本块删除的点数。
- 补图稀疏时:若 接近 ,直接枚举补图边可能更快;两种做法按 与补图边数取较小者。
关联题目
- 01-MST:01-MST 归约为补图连通块数减一。
- CF 920E Connected Components?
- CF 190E Counter Attack