Envy
多次询问一组边能否同时属于某棵 MST;按权值分组,用 Kruskal 的连通块不变性和可撤销并查集判定。来源 Codeforces 891 C · 标签 生成树 / Kruskal / 并查集 / 离线 / 可撤销并查集
题目描述
给定一张 个点、 条边的无向连通图,每条边有边权。有 次询问,每次给出 条边,问这些边能否同时出现在某一棵最小生成树中。
,,所有询问的 之和不超过 。
题解
按边权从小到大执行 Kruskal。需要用到 MST 的两个性质:
- 所有 MST 中,每个权值的边使用的数量固定。
- 对于任意 ,只加入权值小于 的边后,所有 MST 形成的连通块相同。
因此把询问中的边按权值分组,并按权值从小到大处理。
处理权值 时,全局并查集已经加入了所有边权小于 的图边。对每个询问,在它当前权值为 的边上临时做并查集合并:
- 若某条边的两个端点已经连通,说明这些同权边内部成环,该询问不可能同时包含它们,直接标记为不合法;
- 否则临时合并这些边,继续检查下一条。
处理完一个询问的这一组边后,撤销临时合并,避免影响其他询问。等所有权值为 的询问处理完,再把原图中所有权值为 的边正式加入全局并查集。
因为同权边之间只关心“在小于 的连通块上是否成环”,而小于 的连通块对所有 MST 都相同,所以这个判定是充分的。实现时用按大小合并、不路径压缩的可撤销并查集。
复杂度
图边和询问边各排序一次,复杂度 。并查集操作均摊 ,总时间复杂度 加上排序,空间 。