01-MST

完全图边权只有 0/1,给定权值为 1 的边;MST 权值为 0 边补图的连通分量数减 1。

来源 Codeforces 1243 D · 难度 Codeforces 2100 · 标签 图论 / 生成树 / 补图 / BFS

题目描述

给定 𝑛 个点的完全无向图,每条边的权值为 0 或 1。给出其中 𝑚 条权值为 1 的边,其余边权值均为 0。求该图最小生成树的权值和。

1≤𝑛≤105,0≤𝑚≤min(𝑛(𝑛−1)2,105)。

题解

边权只有 0 和 1,所以优先选 0 边。把只由 0 边连接的连通块缩成一个点:块内可以用 0 边连通,块间任取 𝑐−1 条 1 边即可,其中 𝑐 是 0 边图的连通块数。完全图保证块间边一定存在,因此答案为

𝑐−1

问题转化为求给定 1 边图的补图连通块数。补图有 𝑂(𝑛2) 条边,不能显式建图。

用 BFS 和有序集合维护尚未访问的点:

  • 初始时把所有点放入 unvisited;
  • 从 unvisited 取出一个点,作为新连通块的起点,连通块数加一;
  • BFS 中,对队首 𝑢 遍历 unvisited 中的所有 𝑣:

    • 若 (𝑢,𝑣) 不是 1 边,则补图中有 0 边,把 𝑣 从 unvisited 删除并入队;
    • 否则保留 𝑣,继续检查下一个点。

外层继续从 unvisited 取出下一个连通块的起点。

复杂度

每条 1 边最多被检查一次,每个点最多被删除一次,因此总复杂度 𝑂((𝑛+𝑚)log𝑛),空间 𝑂(𝑛+𝑚)。

参考

源码位置