Envy

多次询问一组边能否同时属于某棵 MST;按权值分组,用 Kruskal 的连通块不变性和可撤销并查集判定。

来源 Codeforces 891 C · 标签 生成树 / Kruskal / 并查集 / 离线 / 可撤销并查集

题目描述

给定一张 𝑛 个点、𝑚 条边的无向连通图,每条边有边权。有 𝑄 次询问,每次给出 𝑘𝑖 条边,问这些边能否同时出现在某一棵最小生成树中。

2≤𝑛,𝑚≤5×105,𝑛−1≤𝑚,所有询问的 𝑘𝑖 之和不超过 5×105。

题解

按边权从小到大执行 Kruskal。需要用到 MST 的两个性质:

  • 所有 MST 中,每个权值的边使用的数量固定。
  • 对于任意 𝑡,只加入权值小于 𝑡 的边后,所有 MST 形成的连通块相同。

因此把询问中的边按权值分组,并按权值从小到大处理。

处理权值 𝑤 时,全局并查集已经加入了所有边权小于 𝑤 的图边。对每个询问,在它当前权值为 𝑤 的边上临时做并查集合并:

  • 若某条边的两个端点已经连通,说明这些同权边内部成环,该询问不可能同时包含它们,直接标记为不合法;
  • 否则临时合并这些边,继续检查下一条。

处理完一个询问的这一组边后,撤销临时合并,避免影响其他询问。等所有权值为 𝑤 的询问处理完,再把原图中所有权值为 𝑤 的边正式加入全局并查集。

因为同权边之间只关心“在小于 𝑤 的连通块上是否成环”,而小于 𝑤 的连通块对所有 MST 都相同,所以这个判定是充分的。实现时用按大小合并、不路径压缩的可撤销并查集。

复杂度

图边和询问边各排序一次,复杂度 𝑂(𝑚log𝑚+(∑𝑘𝑖)log(∑𝑘𝑖))。并查集操作均摊 𝑂(𝛼(𝑛)),总时间复杂度 𝑂((𝑚+∑𝑘𝑖)𝛼(𝑛)) 加上排序,空间 𝑂(𝑛+𝑚+∑𝑘𝑖)。

源码位置