709 字
4 分钟
【ACM 算法随笔】并查集的应用

并查集等价类维护#

程序自动化分析#

题目链接

题目要点解析#

金字塔对齐问题#

题目链接

题目要点解析#

移除最多的石头#

题目链接

题目要点解析#

(中介并查集)

可激活最大点数#

题目链接

题目要点解析#

(中介并查集)

又有一道好问题#

题目链接

题目要点解析#

虚点技巧(中介并查集)

最大公约数遍历#

题目链接

题目要点解析#

GCD并查集(枚举因子)(中介并查集)

最大公因数排序#

题目链接

题目要点解析#

GCD并查集(枚举因子)(中介并查集)


并查集连通性维护#

删除后的最大和#

题目链接

题目要点解析#

仅有删边的题目转成加边题(逆向思维)

情侣的牵手难题#

题目链接

题目要点解析#

贪心+并查集

新增道路查询后的最短距离问题#

题目链接

题目要点解析#

区间并查集

二维矩阵集水器#

题目链接

题目要点解析#

连通性维护(困难版)

判断角落可达性#

题目链接

题目要点解析#

连通性维护(困难版)

好路径的总个数#

题目链接

题目要点解析#

增量法+并查集

可获得的总分数#

题目链接

题目要点解析#

增量法+并查集

动态边收缩问题#

题目链接

题目要点解析#

缩点+并查集

受限可达集问题#

题目链接

题目要点解析#

缩点+并查集

减少病毒的传播#

题目链接

题目要点解析#

缩点+并查集


并查集传递性维护#

维护集合元素的相对关系

种类并查集就是取模带权并查集

扩展域并查集可以被种类并查集替代

推导部分和问题#

题目链接

题目要点解析#

除法的求值问题#

题目链接

题目要点解析#

异或带权并查集#

题目链接

题目要点解析#

增量偶权环查询#

题目链接

题目要点解析#

银河英雄的传说#

题目链接

题目要点解析#

甄别食物链问题#

题目链接

题目要点解析#

带权并查集(种类并查集)、扩展域并查集

最小的冲突分配#

题目链接

题目要点解析#

扩展域并查集

敌人敌人是朋友#

题目链接

题目要点解析#

扩展域并查集

区间的奇偶问题#

题目链接

题目要点解析#

真正的取模带权并查集,跟种类并查集和扩展域并查集有区别,但可以用扩展域并查集来做


参考文献列表#

  1. 【OI WiKi】并查集相关知识
【ACM 算法随笔】并查集的应用
https://xingguang641.com/posts/acm/acm-note/disjoint-set-union/
作者
星光
发布于
2026-04-03
许可协议
CC BY-NC-SA 4.0