专栏文章

并查集

ttime_keeper
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqy5yrg
此快照首次捕获于
2025/12/04 12:39
3 个月前
此快照最后确认于
2025/12/04 12:39
3 个月前
查看原文

并查集

  • 一种管理元素所在集合的数据结构。

引入

P3367 【模板】并查集
维护一个数据结构，支持合并集合，查询。
考虑最暴力的做法：
维护 nn 个集合，每次将集合一个一个合并。
复杂度 O(nm)O(nm)。
期望得分：70pts70pts。
我们来观察一下我们要干的操作。
如果我们把每个集合内的元素当做节点，把每个集合当做一颗树。
那这其实是一个森林。
对于合并两个集合，本质上是把点 XX 所在的数的根和点 YY 所在树的根合并。
查询是查询他们两个是不是在同一颗树上。
那么我们又得到了一个做法：
每个点维护自己的父亲节点的编号。
根节点的父亲为自己。
查询的时候只需要向上跳直到根节点，如果他们在一个树内，那么他们所在的这棵树的根节点就相同。
合并只需要将一颗树的根节点练到另一颗树的根节点。
具体的，把一颗树的根节点当做另一颗树根节点的儿子。
分析一下复杂度，不难发现，暴力向上跳的复杂度最劣是 O(n)O(n) 的，合并的时候复杂度是 O(n)O(n) 的（需要先找到根节点）。
那还有哪里能优化呢？
路径压缩
我们注意到，对于每个节点，我们有些时候并不需要真的关心他的父节点是谁，我们要查询的只是他所在树的根节点。
那么就有一个想法，如果说我们把每一个点都直接连到根节点，那么对于处理好的节点，查询就是 O(1)O(1) 的了。
这个东西的复杂度通常是 O(n\ackermann(n))O(n \ackermann(n))
写作 O(nα(n))O(n \alpha(n))
但是这个东西，你不能相信他的时间复杂度。
Tarjan 给出了一种卡到 O(mlog⁡n)O(m \log n) 的方法。
大概的意思就是，对于二项树一直展开，使每次的路径压缩只压缩一个点。
按秩合并
一般用的都是启发式合并，即按树的大小合并。
如果说我们现在有两颗树，要求合并。
把一颗树挂在另一颗身上。
现在我们把小的树挂在大的树上面，需要更新的节点树最小。
我们注意到，这样做的树高最多是 logp+1log_p + 1 其中 pp 是最后树节点数。
不妨这样想:
设 fif_i 表示按秩合并 ii 个点所得树的最大高度。
则有 f1=0,f2=1,f3=1,f4=1...f_1 = 0,f_2 = 1,f_3 = 1,f_4 = 1...
有如下递推：
fn=max⁡1≤i<n(max⁡(fi,fn−i)+[fi=fn−i])f_n = \max_{1\le i < n}(\max(f_i,f_{n - i})+[f_i=f_{n - i}])
则有 fn+1≥fnf_{n + 1} \ge f_n,f2n≥fn+1f_{2n}\ge f_n+1
可以证明 fn=⌊log⁡n⌋f_n = \lfloor \log n\rfloor
对 nn 用数学归纳法。
fn=max⁡1≤i≤n/2fn−i+[fi=fn−i]=max⁡1≤i≤n/2⌊log⁡(n−i)⌋+[⌊log⁡i⌋=⌊log⁡(n−i)⌋]\begin{aligned} f_n &= \max_{1\le i \le n/2} f_{n-i} + [f_i = f_{n-i}] \\ &= \max_{1\le i \le n/2} \lfloor \log (n-i) \rfloor + [\lfloor\log i \rfloor = \lfloor \log(n-i)\rfloor] \end{aligned}
也就是说，按秩合并每次树高最多增加 11。
设 n=2k+in = 2^k + i，其中 0≤i<2k0\le i < 2^k
⌊log⁡i⌋=⌊log⁡(n−i)⌋  ⟹  ⌊log⁡i⌋=⌊log⁡(n−i)⌋=k−1 \lfloor\log i \rfloor = \lfloor \log(n-i)\rfloor \implies \lfloor\log i \rfloor = \lfloor \log(n-i)\rfloor = k-1
故 fn=max⁡(k,hn−1)=k=⌊log⁡n⌋f_n = \max(k, h_{n-1}) = k = \lfloor \log n\rfloor
复杂度 O(nlog⁡(n))O(n\log(n))
建议把路径压缩和按秩合并一起用。
这样的复杂度是 O(nα(n))O(n \alpha(n)) 的
可以防止被卡。
现场写代码（应该不至于调不出来吧???）

带权并查集

我们在刚刚的按秩合并中记录了联通块的大小。
这个 szsz 也是一种权值（权重）。
P1196 [NOI2002] 银河英雄传说
维护每个战舰到队首的距离（即到根的距离）。
不难发现，合并两个树。
在 findfind 的时候。
本质上就是从自己到队首走一遍。
因此在回溯的时候统计答案即可。
P4079 [SDOI2016] 齿轮
容易发现，如果图中没有环，一定合法。
有环的话，当且仅当环上传动比的积为 11 时合法。
这个证明是容易的。
如果 x,yx,y 的传动比为 v1v_1,y,zy,z 的传动比为 v2v_2。
那么 x,zx,z 的传动比为 v1×v2v_1\times v_2。
那么我们就可以考虑并查集的做法。
我们维护权值表示从 ii 到 faifa_i 节点的传动比之积为 tt。
那么相邻两个点之间的传动比就是他们权值的商。
如果加入一条边，而两个端点在同一个集合内，就说明这条边在环上。
用 tutv\dfrac{t_u}{t_v} 是否等于 xy\dfrac{x}{y} 来判断。
如果 u,vu,v 不在一个联通块内。
我们要在 u−vu-v 之间连一条边权为 tt 的边。
  • faufa_u 转 1tu\dfrac{1}{t_u} 圈， uu 转 11 圈。
  • favfa_v 转 1tv\dfrac{1}{t_v} 圈，vv 转 11 圈。
我们需要让 uu 转 xx 圈，使得 vv 转 yy 。也就是让 uu 转 xy\dfrac{x}{y} 圈，vv 转一圈。
把 faufa_u 放到 fvf_v 的儿子上，favfa_v 转 11 圈，vv 转 tvt_v 圈，uu 转 tv×xy\dfrac{t_v \times x}{y} 圈，faufa_u 要转 tv×xtu×y\dfrac{t_v \times x}{t_u \times y} 圈。

离线统计联通块

P1197 [JSOI2008] 星球大战
发现在线做不好做，并查集很难分裂一颗树。
那么我们考虑离线。
把所有询问执行一遍，扒下来。
现在我们有把所有操作执行完的最后的图。
现在我们要支持的就是加边，统计联通块数了。
这个是好做的。
加一条边，如果两个端点都在一个联通块内，那么啥也没用。
如果不在一个联通块内，那么这两个联通块就被合并起来了，联通块个数减一。
双倍:P6121 [USACO16OPEN] Closing the Farm G

种类并查集

在原本的并查集中，我们可以维护的是一对 (u,v)(u,v) 的关系。
P1892 [BOI2003] 团伙
在这里，敌人的敌人是朋友，朋友的朋友是朋友。
那么我们就可以把一个点拆为两分。
一份表示 ii 作为朋友，一份表示 ii 作为敌人。
我们来想一想。
如果 u,vu,v 是朋友，则连接 u,vu,v 和 u+n,v+nu + n,v + n。
那么这就保证了无论我们查询的是 uu 作为朋友还是 uu 作为敌人，都保证了 u,vu,v 是朋友的关系（都在一层里）。
如果 u,vu,v 是敌人，则连接 u+n,vu + n,v 和 v,u+nv,u + n。
就保证了，无论 uu 是作为朋友还是作为敌人，都保证有 u,vu,v 为敌人。
那么来思考是否具有传递性。
如果 x,y,zx,y,z 满足 x,yx,y 互为敌人， y,zy,z 互为敌人。
那么我们会连接 x,y+n,zx,y + n,z 和 x+n,y,z+nx + n,y,z + n。
此时查询 xx 时，x,zx,z 互为朋友（在同一层）， x+n,z+nx + n,z + n 互为朋友（在同一层）。
如果 x,y,zx,y,z 满足 x,yx,y 互为朋友， y,zy,z 互为朋友。
那么 x,y,zx,y,z 和 x+n,y+n,z+nx + n,y + n,z + n 也互为朋友。
满足传递。
所以就可以这么做了。
P2024 [NOI2001] 食物链
同上。
我们要维护 ii 作为同类，ii 作为吃别人的，ii 作为被吃的。
如果 x,yx,y 是同类，那么 xx 作为同类，作为猎物，作为天敌都需要与相应的 yy 连边。
如果 xx 吃 yy 那么：
  • xx 的同类是 yy 的天敌。
  • xx 的猎物是 yy 的同类。
  • xx 的天敌是 yy 的猎物（题面说可以吃回去）。

并查集的 trick

P2391 白雪皑皑
区间染色，最后单点查询。
显然是可以用各种方法做到 O(mlog⁡n)O(m \log n) 的。
但是此题 q≤1e7q \le 1e7。
本着正难则反的思想。
我们把操作倒着做。
CPP
-------(1)
  -------(2)
----(3)
    ---------(4)
如果倒着做，那么之前染过色的区间就不会被再染色了。
那么我们就可以记录每个点之后的第一个未染色的点是哪个。
这样每次我们就只需要从 ll 出发，一直跳到 rr。
对中途未染色的染色。
考虑势能分析。
每一个点最多被更新一次。
所以复杂度为 O(n)O(n)
那问题就变成了如何快速维护一个点后（包括这个点）的第一个未染色的点。
那么我们的操作就形似：
把所有下一个能染色的点为 xx 的点变为 yy。
查询。
容易发现这就是一个并查集。
复杂度 O(mα(n))O(m \alpha(n))

可撤销并查集

我们来思考一下并查集的本质。
在路径压缩的时候，我们把 xx 为根的所有节点放到了 xx 的一级儿子上，这保证了查询要跳的层数很小。
在按秩合并的时候，我们把小的合并到大的上去，并且用势能分析法证明了它的树高最多为 lognlog_n。
但是按秩合并有一个很优美的性质！
我们注意到，按秩合并的 mergemerge 时，只有一个点被修改了，即小树的根的父亲变成了大树的根。
那么我们对 fafa 数组的操作就是 O(1)O(1) 的。
那么我们就可以把每次操作的修改给存下来，压到一个栈里。
如果这次修改不想要了，我们就弹栈顶，顺带回撤修改。
好像没有很简单的可撤销并查集的。
那就放一个可持久化并查集硬做吧。
P3402 可持久化并查集
这个东西当然是可以用可持久化数组+按秩合并做的。
可持久化数组是：我们注意到修改一个点最多修改 logVlog_V 个权值线段树上的节点，所以可以依照之前版本可持久化。（自己写的，不一定准确）
但是真的需要吗？不需要！
我们观察题目难做的地方在哪里？
我们可能撤销撤销的操作（即加入之前撤销的边）。
我们考虑把操作建成一颗树。
如果是 1,31,3 操作的话，就把 i−1i - 1 向 ii 连边。
表示 i−1i-1 执行完就执行 ii。
如果是 22 操作，那么就从 kk 连向 ii 表示 ii 的状态是从 kk 来的。
我们注意到，这个操作树有一个很优美的性质！
对于任意一个点 ii，执行到他的状态是从根到他所有操作执行完的状态。
那么我们就可以用 DFS+\text{DFS}+ 可撤销并查集来做。
具体的，把所有操作扒下来，建出操作树。
然后从根节点开始 DFSDFS 每次进入节点执行操作，出节点回撤操作。
这样我们就能保证到点 ii 时并查集的状态为从根节点执行到 ii 的状态。
然后就得到了一个 O(mlog⁡n)O(m \log n) 的做法。
当然，你也可以用可持久化并查集的做法过掉 NOI2018D1T1。
P4768 [NOI2018] 归程
这个东西是可以用Kruskal重构树上倍增做的。
但是作为学数据结构学傻了的人，我们考虑用可持久化并查集做。
注意注意！这个东西不能用可撤销并查集做！！！
首先我们注意到。
下车之后无论是不是有积水的边都能走，所以下车后一定要走的路程是下车到的点到 11 的最短路。
这个东西一定一定要用 dijkstradijkstra 求！SPFASPFA 就是在这里死掉的！
由于车只能走没有积水的边。
所以我们容易想到一个暴力的想法！
把所有不积水的边塞到并查集里。
维护联通块内到点 11 最短路的最小值。
但显然过不去。
考虑优化。
注意到每次询问给定了一个积水量。
每次只有海拔大于这个积水量的边才有效。
我们把所有边按照海拔排序。
容易发现，一条边只有一个前缀是有效的！
我们把边按照海拔从大到大的加入并查集中。
我们钦定这个顺序就是时间顺序。
显然我们会有 nn 个版本的并查集。
对于每次询问，我们需要知道他在哪个版本的并查集生效了。
然后查询联通块最小值即可。
复杂度 O((q+m)log⁡2n)O((q + m) \log^2 n)
还有一个小优化：
我们并不需要真的一个可持久化并查集。
因为我们没有撤销操作。
所以我们可以用一个可持久化数组直接代替 fafa 数组。
复杂度 O((n+m)log⁡n+qlog⁡2n)O((n + m)\log n + q\log^2 n)
然鹅
如果这个题的询问可以离线。
我们就可以直接用并查集做了！
因为我们只需要按海拔加边，然后查询所有在这个版本生效的询问。
复杂度 O((n+m)log⁡n+mlog⁡m+mα(n))O((n + m) \log n + m \log m + m \alpha(n))

倍增并查集

我也不知道这个东西叫什么。
P3295 [SCOI2016] 萌萌哒
我们维护并查集的联通块表示这一个联通块内的所有位相同。
但是此时需要区间合并。
对于区间合并，我们想到可以用倍增的思想来 log⁡n\log n 拆分区间。
显然并查集的区间是具有结合律的。
所以我们合并 [l1,r1][l_1,r_1] 和 [l2,r2][l_2,r_2]区间，就可以用倍增优化。
设 fi,jf_{i,j} 表示 [i,i+2j−1][i,i + 2^j - 1] 区间内的父亲。
由于恒等式 2i=2i−1+2i−12^i=2^{i-1}+2^{i-1}。
我们在合并的时候只需要将对应 2i2^i 区间合并即可。
比如合并 [2,6][2,6] 和 [7,11][7,11]。
我们要合并 f2,2f_{2,2} 和 f7,2f_{7,2}，即 [2,5][2,5] 和 [7,10][7,10]。
再合并 f6,0f_{6,0} 和 f11,0f_{11,0}，即合并 [6,6][6,6] 和 [11,11][11,11]。
然后在最后，我们从大到小枚举 2i2^i
把这个 fi,jf_{i,j} 的连通性转递给 fi,j−1f_{i,j - 1} 和 fi+2j−1,j−1f_{i + 2^{j-1},j-1}。
最后简单乘法原理。
答案即为 9×10cnt−19\times 10^{cnt-1}。
cntcnt 为联通块数量。
考虑在线化改造：
我们维护 log⁡n\log n 层并查集，用类似 STST 表的方式合并。
在连接 [l1,r1][l1,r1] 和 [l2,r2][l2,r2] 时，像 ST 表一样，拆成两个 2k2^k 的区间合并。
对于一个 2k2^k 的区间合并。
现在第 kk 层查询，如果在一个联通块内，那么直接 return 即可。
如果不在一个联通块内，说明可能会产生效果。
暴力递归到第 k−1k - 1 层。
直到 k=0k = 0 也就是单点的时候，如果还能成功合并，就说明确实没有联通。
注意到如果向下递归，那么这层一定没有成功合并。
每一层成功合并的次数是 n−1n - 1 次。
那么总的成功合并的次数就是 nlog⁡nn \log n 级别的了。
时间复杂度 O(nlog⁡αn)O(n \log\alpha n) 或 O(nlog⁡2n)O(n \log^2 n)
课后作业：
【UR #5】怎样更有力气

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...