709 字
4 分钟
【ACM 算法随笔】并查集的应用
并查集等价类维护
程序自动化分析
题目要点解析
金字塔对齐问题
题目要点解析
移除最多的石头
题目要点解析
(中介并查集)
可激活最大点数
题目要点解析
(中介并查集)
又有一道好问题
题目要点解析
虚点技巧(中介并查集)
最大公约数遍历
题目要点解析
GCD并查集(枚举因子)(中介并查集)
最大公因数排序
题目要点解析
GCD并查集(枚举因子)(中介并查集)
并查集连通性维护
删除后的最大和
题目要点解析
仅有删边的题目转成加边题(逆向思维)
情侣的牵手难题
题目要点解析
贪心+并查集
新增道路查询后的最短距离问题
题目要点解析
区间并查集
二维矩阵集水器
题目要点解析
连通性维护(困难版)
判断角落可达性
题目要点解析
连通性维护(困难版)
好路径的总个数
题目要点解析
增量法+并查集
可获得的总分数
题目要点解析
增量法+并查集
动态边收缩问题
题目要点解析
缩点+并查集
受限可达集问题
题目要点解析
缩点+并查集
减少病毒的传播
题目要点解析
缩点+并查集
并查集传递性维护
维护集合元素的相对关系
种类并查集就是取模带权并查集
扩展域并查集可以被种类并查集替代
推导部分和问题
题目要点解析
除法的求值问题
题目要点解析
异或带权并查集
题目要点解析
增量偶权环查询
题目要点解析
银河英雄的传说
题目要点解析
甄别食物链问题
题目要点解析
带权并查集(种类并查集)、扩展域并查集
最小的冲突分配
题目要点解析
扩展域并查集
敌人敌人是朋友
题目要点解析
扩展域并查集
区间的奇偶问题
题目要点解析
真正的取模带权并查集,跟种类并查集和扩展域并查集有区别,但可以用扩展域并查集来做
参考文献列表
【ACM 算法随笔】并查集的应用
https://xingguang641.com/posts/acm/acm-note/disjoint-set-union/