本地源文件：docs/topic__dsu-app.md

并查集应用

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

A

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

接下来有 𝑚m 次加边操作，第 𝑖i 次操作在 𝑎𝑖ai 和 𝑏𝑖bi 之间加一条无向边．设 𝐿(𝑖,𝑗)L(i,j) 表示结点 𝑖i 和 𝑗j 最早在第 𝐿(𝑖,𝑗)L(i,j) 次操作后连通．

在 𝑚m 次操作完后，你要求出 ∑𝑛𝑖=1∑𝑛𝑗=𝑖+1𝐿(𝑖,𝑗)∑i=1n∑j=i+1nL(i,j) 的值．

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

B

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

接下来有 𝑚m 次加边操作，第 𝑖i 次操作在 𝑎𝑖ai 和 𝑏𝑖bi 之间加一条无向边．

接下来有 𝑞q 次询问，第 𝑖i 次询问 𝑢𝑖ui 和 𝑣𝑖vi 最早在第几次操作后连通．

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

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

C

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

接下来有 𝑚m 次加边操作，第 𝑖i 次操作在 𝑎𝑖ai 和 𝑏𝑖bi 之间加一条无向边．

接下来有 𝑞q 次询问，第 𝑖i 次询问第 𝑥𝑖xi 个点在第 𝑡𝑖ti 次操作后所在连通块的大小．

离线算法：考虑将询问按 𝑡𝑖ti 从小到大排序．在加边的过程中使用并查集顺便处理询问即可．时间复杂度 𝑂(𝑞log⁡𝑞 +(𝑛 +𝑞)𝛼(𝑛))O(qlog⁡q+(n+q)α(n))．

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

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

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

D

给一个长度为 𝑛n 的 01 序列 𝑎1,…,𝑎𝑛a1,…,an，一开始全是 00，接下来进行 𝑚m 次操作：

令 𝑎𝑥 =1ax=1；
求 𝑎𝑥,𝑎𝑥+1,…,𝑎𝑛ax,ax+1,…,an 中左数第一个为 00 的位置．

建立一个并查集，𝑓𝑖fi 表示 𝑎𝑖,𝑎𝑖+1,…,𝑎𝑛ai,ai+1,…,an 中第一个 00 的位置．初始时 𝑓𝑖 =𝑖fi=i．

对于一次 𝑎𝑥 =1ax=1 的操作，如果 𝑎𝑥ax 原本就等于 11，就不管．否则我们令 𝑓𝑥 =𝑓𝑥+1fx=fx+1．

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

E

给出三个长度为 𝑛n 的正整数序列 𝑎a，𝑏b，𝑐c．枚举 1 ≤𝑖 ≤𝑗 ≤𝑛1≤i≤j≤n，求 𝑎𝑖 ⋅𝑏𝑗 ⋅min𝑖≤𝑘≤𝑗𝑐𝑘ai⋅bj⋅mini≤k≤jck 的最大值．

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

F

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

加一条从 𝑎𝑖ai 到 𝑏𝑖bi 的边．
询问两个点 𝑢𝑖ui 和 𝑣𝑖vi 之间是否有至少两条边不相交的路径．

询问可以转化为：求 𝑢𝑖ui 和 𝑣𝑖vi 是否在同一个简单环上．按照双连通分量缩点的想法，每次我们在 𝑎𝑖ai 和 𝑏𝑖bi 间加一条边，就可以把 𝑎𝑖ai 到 𝑏𝑖bi 树上路径的点缩到一起．如果两条边 (𝑎𝑖,𝑏𝑖)(ai,bi) 和 (𝑎𝑗,𝑏𝑗)(aj,bj) 对应的树上路径有交，那么这两条边就会被缩到一起．

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

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

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

G

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

接下来有 𝑚m 次加边操作，第 𝑖i 次操作在 𝑎𝑖ai 和 𝑏𝑖bi 之间加一条无向边．

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

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

强制在线．

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

如果第 𝑖i 次操作 𝑎𝑖ai 和 𝑏𝑖bi 属于同一个连通块，那么我们就需要将边双树上 𝑎𝑖ai 到 𝑏𝑖bi 路径上的点缩起来．这可以用并查集维护．每次缩点，边双连通分量的个数减少 11，最多减少 𝑛 −1n−1 次，因此缩点部分的并查集复杂度是 𝑂(𝑛𝛼(𝑛))O(nα(n))．

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

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

综上，该算法的总复杂度是 𝑂(𝑛log⁡𝑛 +𝑚log⁡𝑛)O(nlog⁡n+mlog⁡n) 的．

小结

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

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

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