当前位置: 首页 > news >正文

浅谈并查集

带权并查集

Luogu P2024

经典例题食物链。

题意:\(n\) 个动物,可能是三个物种之一,给出若干描述,形如两个动物是同类或是吃与被吃的关系,确定出矛盾的描述。

考虑建图,有边相连代表确定一个确定另一个关系,这是常用技巧。

物种体现在边权上,边权 \(0/1/2\) 表示在三个物种的三元环上,两个点之间要走多少步才能到达。

带权并查集,维护到根的路径上的边权和(模 3 加法群),即可判断描述的合法性。

并查集维护序列连通性

并查集可以维护图的连通性,我们拓展到序列上也是类似的。

并查集维护序列连通性一般是维护形如下一个满足某条件的位置是什么。

例题:Luogu P2391 白雪皑皑

题意是对序列进行若干次染色,求每个位置最后的颜色。

染色问题有技巧反着考虑,直接得到最终状态。

那么转换为,要快速找到每个位置下一个没有染色的位置,这符合并查集维护序列连通性的基本要求。

我们更改并查集 \(fa_i\) 的定义为上述所求。

倒序枚举询问,从前往后跳,每次将跳到的位置标记颜色,并更新当前的 \(fa_i \leftarrow fa_{i + 1}\),意义为当前位置染色完了,从下一个位置的答案更新。

注意到每个位置只会被跳一次,那么复杂度即为 \(O(n \alpha(n))\)

其实我们相当于维护每个位置下一个没有染色的位置相当于维护了一个链表,更新也符合链表的操作,区别仅仅体现为路径压缩加快查询链表尾端。

可撤销并查集

并查集不能快速分裂,只能快速撤销。

可撤销并查集不能路径压缩,因为我们在路径压缩时实际上是损失了树的结构的信息,于是我们用按秩合并加快并查集速度。

用一个栈维护操作序,每次撤销就弹出栈顶并更新成原来的值。

可撤销并查集一般应用于类似线段树分治、操作分块等按时间轴分治的一些数据结构(与图相关的)

代码

没有什么并查集裸题,贴个可撤销带权并查集(来自线段树分治板子)

http://www.hskmm.com/?act=detail&tid=25659

相关文章:

  • 16_AiAgentMCP简单教程
  • 17_AiAgentMCP实现技术选型
  • JVM_XMS 和 java_opts哪种写法对?如何在JVM中设置JVM_XMS和java_opts?
  • POLIR-Society-Philosophy-mind: 思想/精神
  • 鸿蒙编译ffmpeg库 - 详解
  • 知道却做不到
  • 题解:loj154 集合划分计数
  • 为什么 Java 中打印Object类型的变量无需强转,而从Object类型的数组中取元素却要强转?
  • WinReanimator恶意软件清除指南:详细步骤与工具使用
  • 251006
  • 2025国庆Day5
  • 字节跳动开源图标库:2000+图标一键换肤的魔法 - 教程
  • 换根DP学习笔记
  • 自动化数据操作平台获3000万美元融资
  • 模块
  • 实用指南:【相机基础知识与物体检测】更新中
  • AtCoder Beginner Contest 422 游记(VP)
  • 详细介绍:无人机光纤FC接口模块技术分析
  • 2025 --【J+S 二十连测】-- 第十三套 总结
  • 文件提供的基本操作
  • 深入解析:MySQL(50)如何使用UNSIGNED属性?
  • 迈向人机价值共生文明:AI元人文范式下的演化架构与协同治理
  • 10.6
  • 文件存储空间管理
  • 详细介绍:关于ios点击分享自动复制到粘贴板的问题
  • 新一代数据平台替代传统大数据技术栈
  • 攻击者如何绕过macOS内置安全防护机制
  • 在A列连续且相等行的最后插入空行,并求和
  • 10.6集训改错
  • @Prometheus 监控-MySQL (Mysqld Exporter) - 教程