并查集

· · 个人记录

并查集

引入

P3367 【模板】并查集

维护一个数据结构，支持合并集合，查询。

考虑最暴力的做法：

维护 n 个集合，每次将集合一个一个合并。

复杂度 O(nm)。

期望得分：70pts。

我们来观察一下我们要干的操作。

如果我们把每个集合内的元素当做节点，把每个集合当做一颗树。

那这其实是一个森林。

对于合并两个集合，本质上是把点 X 所在的数的根和点 Y 所在树的根合并。

查询是查询他们两个是不是在同一颗树上。

那么我们又得到了一个做法：

每个点维护自己的父亲节点的编号。

根节点的父亲为自己。

查询的时候只需要向上跳直到根节点，如果他们在一个树内，那么他们所在的这棵树的根节点就相同。

合并只需要将一颗树的根节点练到另一颗树的根节点。

具体的，把一颗树的根节点当做另一颗树根节点的儿子。

分析一下复杂度，不难发现，暴力向上跳的复杂度最劣是 O(n) 的，合并的时候复杂度是 O(n) 的（需要先找到根节点）。

那还有哪里能优化呢？

路径压缩

我们注意到，对于每个节点，我们有些时候并不需要真的关心他的父节点是谁，我们要查询的只是他所在树的根节点。

那么就有一个想法，如果说我们把每一个点都直接连到根节点，那么对于处理好的节点，查询就是 O(1) 的了。

这个东西的复杂度通常是 O(n \ackermann(n))

写作 O(n \alpha(n))

但是这个东西，你不能相信他的时间复杂度。

Tarjan 给出了一种卡到 O(m \log n) 的方法。

大概的意思就是，对于二项树一直展开，使每次的路径压缩只压缩一个点。

按秩合并

一般用的都是启发式合并，即按树的大小合并。

如果说我们现在有两颗树，要求合并。

把一颗树挂在另一颗身上。

现在我们把小的树挂在大的树上面，需要更新的节点树最小。

我们注意到，这样做的树高最多是 log_p + 1 其中 p 是最后树节点数。

不妨这样想:

设 f_i 表示按秩合并 i 个点所得树的最大高度。

则有 f_1 = 0,f_2 = 1,f_3 = 1,f_4 = 1...

有如下递推：

f_n = \max_{1\le i < n}(\max(f_i,f_{n - i})+[f_i=f_{n - i}])

则有 f_{n + 1} \ge f_n,f_{2n}\ge f_n+1

可以证明 f_n = \lfloor \log n\rfloor

对 n 用数学归纳法。

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}

也就是说，按秩合并每次树高最多增加 1。

设 n = 2^k + i，其中 0\le i < 2^k

\lfloor\log i \rfloor = \lfloor \log(n-i)\rfloor \implies \lfloor\log i \rfloor = \lfloor \log(n-i)\rfloor = k-1

故 f_n = \max(k, h_{n-1}) = k = \lfloor \log n\rfloor

复杂度 O(n\log(n))

建议把路径压缩和按秩合并一起用。

这样的复杂度是 O(n \alpha(n)) 的

可以防止被卡。

现场写代码（应该不至于调不出来吧???）

带权并查集

我们在刚刚的按秩合并中记录了联通块的大小。

这个 sz 也是一种权值（权重）。

P1196 [NOI2002] 银河英雄传说

维护每个战舰到队首的距离（即到根的距离）。

不难发现，合并两个树。

在 find 的时候。

本质上就是从自己到队首走一遍。

因此在回溯的时候统计答案即可。

P4079 [SDOI2016] 齿轮

容易发现，如果图中没有环，一定合法。

有环的话，当且仅当环上传动比的积为 1 时合法。

这个证明是容易的。

如果 x,y 的传动比为 v_1,y,z 的传动比为 v_2。

那么 x,z 的传动比为 v_1\times v_2。

那么我们就可以考虑并查集的做法。

我们维护权值表示从 i 到 fa_i 节点的传动比之积为 t。

那么相邻两个点之间的传动比就是他们权值的商。

如果加入一条边，而两个端点在同一个集合内，就说明这条边在环上。

用 \dfrac{t_u}{t_v} 是否等于 \dfrac{x}{y} 来判断。

如果 u,v 不在一个联通块内。

我们要在 u-v 之间连一条边权为 t 的边。

我们需要让 u 转 x 圈，使得 v 转 y 。也就是让 u 转 \dfrac{x}{y} 圈，v 转一圈。

把 fa_u 放到 f_v 的儿子上，fa_v 转 1 圈，v 转 t_v 圈，u 转 \dfrac{t_v \times x}{y} 圈，fa_u 要转 \dfrac{t_v \times x}{t_u \times y} 圈。

离线统计联通块

P1197 [JSOI2008] 星球大战

发现在线做不好做，并查集很难分裂一颗树。

那么我们考虑离线。

把所有询问执行一遍，扒下来。

现在我们有把所有操作执行完的最后的图。

现在我们要支持的就是加边，统计联通块数了。

这个是好做的。

加一条边，如果两个端点都在一个联通块内，那么啥也没用。

如果不在一个联通块内，那么这两个联通块就被合并起来了，联通块个数减一。

双倍:P6121 [USACO16OPEN] Closing the Farm G

种类并查集

在原本的并查集中，我们可以维护的是一对 (u,v) 的关系。

P1892 [BOI2003] 团伙

在这里，敌人的敌人是朋友，朋友的朋友是朋友。

那么我们就可以把一个点拆为两分。

一份表示 i 作为朋友，一份表示 i 作为敌人。

我们来想一想。

如果 u,v 是朋友，则连接 u,v 和 u + n,v + n。

那么这就保证了无论我们查询的是 u 作为朋友还是 u 作为敌人，都保证了 u,v 是朋友的关系（都在一层里）。

如果 u,v 是敌人，则连接 u + n,v 和 v,u + n。

就保证了，无论 u 是作为朋友还是作为敌人，都保证有 u,v 为敌人。

那么来思考是否具有传递性。

如果 x,y,z 满足 x,y 互为敌人， y,z 互为敌人。

那么我们会连接 x,y + n,z 和 x + n,y,z + n。

此时查询 x 时，x,z 互为朋友（在同一层）， x + n,z + n 互为朋友（在同一层）。

如果 x,y,z 满足 x,y 互为朋友， y,z 互为朋友。

那么 x,y,z 和 x + n,y + n,z + n 也互为朋友。

满足传递。

所以就可以这么做了。

P2024 [NOI2001] 食物链

同上。

我们要维护 i 作为同类，i 作为吃别人的，i 作为被吃的。

如果 x,y 是同类，那么 x 作为同类，作为猎物，作为天敌都需要与相应的 y 连边。

如果 x 吃 y 那么：

并查集的 trick

P2391 白雪皑皑

区间染色，最后单点查询。

显然是可以用各种方法做到 O(m \log n) 的。

但是此题 q \le 1e7。

本着正难则反的思想。

我们把操作倒着做。

-------(1)
  -------(2)
----(3)
    ---------(4)

如果倒着做，那么之前染过色的区间就不会被再染色了。

那么我们就可以记录每个点之后的第一个未染色的点是哪个。

这样每次我们就只需要从 l 出发，一直跳到 r。

对中途未染色的染色。

考虑势能分析。

每一个点最多被更新一次。

所以复杂度为 O(n)

那问题就变成了如何快速维护一个点后（包括这个点）的第一个未染色的点。

那么我们的操作就形似：

把所有下一个能染色的点为 x 的点变为 y。

查询。

容易发现这就是一个并查集。

复杂度 O(m \alpha(n))

可撤销并查集

我们来思考一下并查集的本质。

在路径压缩的时候，我们把 x 为根的所有节点放到了 x 的一级儿子上，这保证了查询要跳的层数很小。

在按秩合并的时候，我们把小的合并到大的上去，并且用势能分析法证明了它的树高最多为 log_n。

但是按秩合并有一个很优美的性质！

我们注意到，按秩合并的 merge 时，只有一个点被修改了，即小树的根的父亲变成了大树的根。

那么我们对 fa 数组的操作就是 O(1) 的。

那么我们就可以把每次操作的修改给存下来，压到一个栈里。

如果这次修改不想要了，我们就弹栈顶，顺带回撤修改。

好像没有很简单的可撤销并查集的。

那就放一个可持久化并查集硬做吧。

P3402 可持久化并查集

这个东西当然是可以用可持久化数组+按秩合并做的。

可持久化数组是：我们注意到修改一个点最多修改 log_V 个权值线段树上的节点，所以可以依照之前版本可持久化。（自己写的，不一定准确）

但是真的需要吗？不需要！

我们观察题目难做的地方在哪里？

我们可能撤销撤销的操作（即加入之前撤销的边）。

我们考虑把操作建成一颗树。

如果是 1,3 操作的话，就把 i - 1 向 i 连边。

表示 i-1 执行完就执行 i。

如果是 2 操作，那么就从 k 连向 i 表示 i 的状态是从 k 来的。

我们注意到，这个操作树有一个很优美的性质！

对于任意一个点 i，执行到他的状态是从根到他所有操作执行完的状态。

那么我们就可以用 \text{DFS}+ 可撤销并查集来做。

具体的，把所有操作扒下来，建出操作树。

然后从根节点开始 DFS 每次进入节点执行操作，出节点回撤操作。

这样我们就能保证到点 i 时并查集的状态为从根节点执行到 i 的状态。

然后就得到了一个 O(m \log n) 的做法。

当然，你也可以用可持久化并查集的做法过掉 NOI2018D1T1。

P4768 [NOI2018] 归程

这个东西是可以用Kruskal重构树上倍增做的。

但是作为学数据结构学傻了的人，我们考虑用可持久化并查集做。

注意注意！这个东西不能用可撤销并查集做！！！

首先我们注意到。

下车之后无论是不是有积水的边都能走，所以下车后一定要走的路程是下车到的点到 1 的最短路。

这个东西一定一定要用 dijkstra 求！SPFA 就是在这里死掉的！

由于车只能走没有积水的边。

所以我们容易想到一个暴力的想法！

把所有不积水的边塞到并查集里。

维护联通块内到点 1 最短路的最小值。

但显然过不去。

考虑优化。

注意到每次询问给定了一个积水量。

每次只有海拔大于这个积水量的边才有效。

我们把所有边按照海拔排序。

容易发现，一条边只有一个前缀是有效的！

我们把边按照海拔从大到大的加入并查集中。

我们钦定这个顺序就是时间顺序。

显然我们会有 n 个版本的并查集。

对于每次询问，我们需要知道他在哪个版本的并查集生效了。

然后查询联通块最小值即可。

复杂度 O((q + m) \log^2 n)

还有一个小优化：

我们并不需要真的一个可持久化并查集。

因为我们没有撤销操作。

所以我们可以用一个可持久化数组直接代替 fa 数组。

复杂度 O((n + m)\log n + q\log^2 n)

然鹅

如果这个题的询问可以离线。

我们就可以直接用并查集做了！

因为我们只需要按海拔加边，然后查询所有在这个版本生效的询问。

复杂度 O((n + m) \log n + m \log m + m \alpha(n))

倍增并查集

我也不知道这个东西叫什么。

P3295 [SCOI2016] 萌萌哒

我们维护并查集的联通块表示这一个联通块内的所有位相同。

但是此时需要区间合并。

对于区间合并，我们想到可以用倍增的思想来 \log n 拆分区间。

显然并查集的区间是具有结合律的。

所以我们合并 [l_1,r_1] 和 [l_2,r_2]区间，就可以用倍增优化。

设 f_{i,j} 表示 [i,i + 2^j - 1] 区间内的父亲。

由于恒等式 2^i=2^{i-1}+2^{i-1}。

我们在合并的时候只需要将对应 2^i 区间合并即可。

比如合并 [2,6] 和 [7,11]。

我们要合并 f_{2,2} 和 f_{7,2}，即 [2,5] 和 [7,10]。

再合并 f_{6,0} 和 f_{11,0}，即合并 [6,6] 和 [11,11]。

然后在最后，我们从大到小枚举 2^i

把这个 f_{i,j} 的连通性转递给 f_{i,j - 1} 和 f_{i + 2^{j-1},j-1}。

最后简单乘法原理。

答案即为 9\times 10^{cnt-1}。

考虑在线化改造： 我们维护 $\log n$ 层并查集，用类似 $ST$ 表的方式合并。 在连接 $[l1,r1]$ 和 $[l2,r2]$ 时，像 ST 表一样，拆成两个 $2^k$ 的区间合并。 对于一个 $2^k$ 的区间合并。 现在第 $k$ 层查询，如果在一个联通块内，那么直接 `return` 即可。 如果不在一个联通块内，说明可能会产生效果。 暴力递归到第 $k - 1$ 层。 直到 $k = 0$ 也就是单点的时候，如果还能成功合并，就说明确实没有联通。 注意到如果向下递归，那么这层一定没有成功合并。 每一层成功合并的次数是 $n - 1$ 次。 那么总的成功合并的次数就是 $n \log n$ 级别的了。 时间复杂度 $O(n \log\alpha n)$ 或 $O(n \log^2 n)

课后作业：

【UR #5】怎样更有力气