并查集应用

并查集，Kruskal 重构树的思维方式是很类似的，他们都能用于处理与连通性有关的问题。本文通过例题讲解的方式给大家介绍并查集思想的应用。

A

有个点，初始时均为孤立点。

接下来有次加边操作，第次操作在和之间加一条无向边。设表示结点和最早在第次操作后连通。

在次操作完后，你要求出 $\sum_{i=1}^n\sum_{j=i+1}^nL(i,j)$ 的值。

这是基础并查集的应用，并查集记录一下子树的大小。考虑统计每次操作的贡献。如果第次操作和分属于两个不同子树，就将这两个子树合并，并将两者子树大小的乘积乘上累加到答案里。时间复杂度 $O(n\alpha(n))$ 。

B

有个点，初始时均为孤立点。

接下来有次加边操作，第次操作在和之间加一条无向边。

接下来有次询问，第次询问和最早在第几次操作后连通。

考虑在并查集合并的时候记录「并查集生成树」，也就是说如果第次操作和分属于两个不同子树，那么把这条边纳入生成树中。边权是。那么查询就是询问到路径上边权的最大值，可以使用树上倍增或者树链剖分的方法维护。时间复杂度 $O(n\log n)$ 。

另外一个方法是维护 Kruskal 重构树，其本质与并查集生成树是相同的。复杂度亦相同。

C

有个点，初始时均为孤立点。

接下来有次加边操作，第次操作在和之间加一条无向边。

接下来有次询问，第次询问第个点在第次操作后所在连通块的大小。

离线算法：考虑将询问按从小到大排序。在加边的过程中顺便处理询问即可。时间复杂度 $O(q\log q+(n+q)\alpha(n))$ 。

在线算法：本题的在线算法只能使用 Kruskal 重构树。Kruskal 重构树与并查集的区别是：第次操作和分属于两个不同子树，那么 Kruskal 会新建一个结点，然后让所在子树的根和所在子树的根分别连向，作为的两个儿子。不妨设的点权是。对于初始的个点，点权为。

对于询问，我们只需要求出在重构树中最大的一个连通块使得连通中的点权最大值不超过，询问的答案就是这个连通块中点权为的结点个数，即叶子结点个数。

由于我们操作的编号是递增的，因此重构树上父结点的点权总是大于子结点的点权。这意味着我们可以在重构树上从到根结点的路径上倍增找到点权最大的不超过的结点。这样我们就求出了答案。时间复杂度 $O(n\log n)$ 。

D

给一个长度为的 01 序列 $a_1,\ldots,a_n$ ，一开始全是，接下来进行次操作：

令；
求 $a_x,a_{x+1},\ldots,a_n$ 中左数第一个为的位置。

建立一个并查集，表示 $a_i,a_{i+1},\ldots,a_n$ 中第一个的位置。初始时。

对于一次的操作，如果原本就等于，就不管。否则我们令 $f_x=f_{x+1}$ 。

时间复杂度 $O(n\log n)$ ，如果要使用按秩合并的话实现会较为麻烦，不过仍然可行。也就是说时间复杂度或为 $O(n\alpha(n))$ 。

E

给出三个长度为的正整数序列，，。枚举 $1\le i\le j\le n$ ，求 $a_i\cdot b_j\cdot \min_{i\le k\le j}c_k$ 的最大值。

本题同样有许多做法，这里我们重点讲解并查集思路。按权值从大到小考虑。相当于我们在上加入一个点，然后将和位置上的点所在的连通块与之合并（如果这两个位置上有点的话）。连通块上记录的最大值和的最大值，即可在合并的时候更新答案。时间复杂度 $O(n\log n)$ 。

F

给出一棵个点的树，接下来有次操作：

加一条从到的边。
询问两个点和之间是否有至少两条边不相交的路径。

询问可以转化为：求和是否在同一个简单环上。按照双连通分量缩点的想法，每次我们在和间加一条边，就可以把到树上路径的点缩到一起。如果两条边和对应的树上路径有交，那么这两条边就会被缩到一起。

换言之，加边操作可以理解为，将到树上路径的边覆盖一次。而询问就转化为了：判断到路径上是否存在未被覆盖的边。如果不存在，那么和就属于同一个双连通分量，也就属于同一个简单环。

考虑使用并查集维护。给树定根，设表示到根的路径中第一个未被覆盖的边。那么每次加边操作，我们就暴力跳并查集。覆盖了一条边后，将这条边对应结点的与父节点合并。这样，每条边至多被覆盖一次，总复杂度 $O(n\log n)$ 。使用按秩合并的并查集同样可以做到 $O(n\alpha(n))$ 。

本题的维护方式类似于 D 的树上版本。

G

无向图有个点，初始时均为孤立点（即没有边）。

接下来有次加边操作，第次操作在和之间加一条无向边。

每次操作后，你均需要求出图中桥的个数。

桥的定义为：对于一条中的边，如果删掉它会使得连通块数量增加，则被称作桥。

强制在线。

本题考察对并查集性质的理解。考虑用并查集维护连通情况。对于边双树，考虑维护有根树，设表示结点的父亲。也就是不带路径压缩的并查集。

如果第次操作和属于同一个连通块，那么我们就需要将边双树上到路径上的点缩起来。这可以用并查集维护。每次缩点，边双连通分量的个数减少，最多减少次，因此缩点部分的并查集复杂度是 $O(n\alpha(n))$ 。

为了缩点，我们要先求出和在边双树上的 LCA。对此我们可以维护一个标记数组。然后从和开始轮流沿着祖先一个一个往上跳，并标记沿途经过的点。一但跳到了某个之前就被标记过的点，那么这个点就是和的 LCA。这个算法的复杂度与到的路径长度是线性相关的，可以接受。

如果和分属于两个不同连通块，那么我们将这两个连通块合并，并且桥的数量加。此时我们需要将两个点所在的边双树连起来，也就是加一条到的边。因此我们需要将其中一棵树重新定根，然后接到另一棵树上。这里运用启发式合并的思想：我们把结点数更小的重新定根。这样的总复杂度是 $O(n\log n)$ 的。

综上，该算法的总复杂度是 $O(n\log n+m\log n)$ 的。

小结

并查集与 Kruskal 重构树有许多共通点，而并查集的优化（按秩合并）正是启发式合并思想的应用。因此灵活运用并查集可以方便地处理许多与连通性有关的图论问题。

本页面部分内容译自博文 Поиск мостов в режиме онлайн 与其英文翻译版 Finding Bridges Online。其中俄文版版权协议为 Public Domain + Leave a Link；英文版版权协议为 CC-BY-SA 4.0。

本页面最近更新：2021/2/8 18:02:48，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：sshwy, Enter-tainer
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用