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

【数据结构】可撤销并查集 - Slayer

可撤销并查集只可以按照加入的时间从后到前撤销加边操作。

具体的,我们会把所有加入的边压入一个栈,然后当什么时候要撤销时不断从栈顶弹出一条边,撤销掉。而至于具体的撤销步骤,我们假设此边原来是把 y 连向 x,那么我们直接把 y 的父亲设为 y 本身,因为在合并两个集合时是把两个端点都执行了一遍找祖先的操作,所以 y 必定作为其原集合的祖先。我们再把 x 的子树大小减去一个 y 的子树大小,那么就还原成功了。

那么对于一条边为什么一定要是有顺序的撤销呢?如果不是按出栈的顺序撤销,那么必定有比他晚一些连边的集合的大小没法维护,所以必须按出栈顺序撤销。

fromzac

int find(int x){return x==fa[x]:x:find(fa[x]);}void merge(int u,int v){int fu=find(u),fv=find(v);if(fu==fv){return ;}if(sz[fu]<sz[fv]){swap(fu,fv);}stk[++top]=fv;fa[fv]=fu;sz[fu]+=sz[fv];
}void del(){if(!top)return  ;int v=stk[top];top--;sz[fa[fv]]-=sz[fv];fa[fv]=fv;
}while(top>tmp)del();
http://www.hskmm.com/?act=detail&tid=27554

相关文章:

  • 皮卡鱼源码导读
  • 高斯消元学习笔记
  • newDay07
  • 10月9日
  • 从开放重定向到XSS:漏洞升级实战
  • 余弦日记
  • 【题解】P11459 [USACO24DEC] Its Mooin Time P
  • 创建一个springboot项目,mybatis连接嵌入式数据库H2,实现增删改查功能
  • 基于众包的产品质量比较与推荐算法研究
  • 10/9
  • 2025.10.9
  • 线程池总结
  • 合并两个有序链表
  • 深入解析:一款相机是只有桶形畸变 和 枕形畸变的一种,还是两个都有?
  • 数据结构-链表
  • 重组抗体技术:从原理到应用,解锁高效可控的新一代抗体研发
  • P13690 [CEOI 2025] boardgames
  • CSS
  • 关于jinja2的ssti模版注入的学习+过滤
  • WPF Epplus export 10M+ items in excel with multiple sheets batch by batch
  • [EGOI 2023] Guessing Game
  • CF2152G Query Jungle
  • [ROI 2018] Addition without carry
  • [THUPC 2025 决赛] Im Here
  • 解码Linux基础命令
  • 基于 C++ 的高雷诺数湍流直接数值模拟求解器设计与性能优化 - 实践
  • 由等概率(a,b)生成等概率(c,d)
  • AI/LLM应用安全与合规产品(AI安全网关|AI安全围栏|AI应用防火墙) 2025最新推荐
  • 10.8 CSP-S模拟27 改题记录
  • 《可复制的领导力》