Dsu app

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

A

A

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

接下来有 m 次加边操作，第 i 次操作在 a_i 和 b_i 之间加一条无向边。设 L(i,j) 表示结点 i 和 j 最早在第 L(i,j) 次操作后连通。

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

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

B

B

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

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

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

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

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

C

C

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

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

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

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

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

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

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

D

D

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

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

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

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

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

E

E

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

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

F

F

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

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

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

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

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

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

G

G

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

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

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

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

强制在线。

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

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

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

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

buildLast update and/or translate time of this article，Check the history
editFound smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github
peopleContributor of this article sshwy
translateTranslator of this article Visit the original article!
copyrightThe article is available under CC BY-SA 4.0 & SATA ; additional terms may apply.

Comments