5
0

《并查集》一节习题笔记(三)

2026-11-16
2026-11-16

本文记录了作者学习罗勇军《算法竞赛》中《高级数据结构》一章《并查集》一节时,完成部分习题的笔记。

洛谷 P1111 - 修复公路

题意

给定一个含有 N 个点的无向图。有 M 条边,每条边由一个三元组 (x, y, t) 描述,代表这条边连接点 x 和 y,并在 t 时刻被启用。给出这些边,从 0 时刻起陆续启用这些边。求这个图连通的最早时刻;若无法连通,输出 -1。

思路

根据最小的连通图这一信息很容易想到最小生成树。一般地 Kruskal 最小生成树算法是按边权排序,这里根据题意按时间对边进行排序。如果添加一条边后,集合个数变为 1,代表图已连通,答案即为这条边的 t。如果最后集合个数仍然大于 1,代表图无法连通,输出 -1。

由于每次遍历一遍所有点统计集合个数可能超时,可以维护一个集合个数变量 cnt,初始化为 N。在合并两个集合时,如果 x 和 y 的根节点 r_x 和 r_y 不相同,需要合并,将 cnt 减 1 即可。

洛谷 P3958 - 奶酪

题意

有一个长宽无限、高为 h 的立方体,其下表面 x = 0,上表面 z = h。这个立方体内有若干个半径为 r 的球形空洞。现在要从下表面去到上表面。如果两个空洞相交或相切,则可以从一个空洞去到另一个空洞。特别地,如果一个空洞与下表面相交或相切,则可以从下表面进入空洞;如果一个空洞与上表面相交或相切,则可以从空洞进入上表面。给出所有空洞的中心坐标,判断是否能够从下表面通过空洞进入上表面。

思路

相交或相切的空洞间可以互相游走,因此可以把相交或相切的空洞合并入一个集合。两个球相交或相切的条件是它们球心的欧几里得距离 d 与半径 r 满足 d \leq 2r,为了避免浮点数精度误差,我们可以直接比较 d^2 和 4r^2 的大小关系。根据上面的思路对空洞进行合并。

显然,z - r \leq 0 时,这个空洞与下表面相连;z + r \geq h 时,这个空洞与上表面相连。可以将与上、下表面相连的空洞分别用两个数组记录。在所有空洞合并完后再枚举,找出是否有与下表面相连的空洞 i 和与上表面相连的空洞 j 满足 \operatorname{find}(i) = \operatorname{find}(j) 即可。

洛谷 P1525 - 关押罪犯

题意

有 N 名罪犯(由 1 \sim N 编号)和 M 组仇恨关系。每组仇恨关系由一个三元组 (a, b, c) 描述,代表 a 号罪犯和 b 号罪犯之间有仇恨,怨气值为 c。要将 N 名罪犯安排至两个监狱。如果将有仇恨关系的两个罪犯安排在一个监狱,那么会产生与他们仇恨关系怨气值相等的事件影响力。现在要适当安排罪犯所监狱,使得所有事件影响力的最大值最小。

思路

有互斥关系,使用扩展域并查集解决。对所有仇恨关系按照怨气值大小从大到小进行排序,先处理怨气值大的仇恨关系。如果两名罪犯此前不在同一个监狱里(或还没有安排监狱),就把他们安排到不同的两个监狱里(互斥关系);否则,代表两个罪犯之间会产生事件影响力,直接输出这一组仇恨关系的怨气值。如果从头到尾都不存在两个罪犯安排至同一个监狱的情况,输出 0 即可。

洛谷 P4185 - MooTube G

题意

有一棵含有 N 个节点和 N - 1 条边的树,树上的任意两个点都可以通过唯一的一条简单连通路径互相到达。每条边有一个权值,定义 i 和 j 两个节点的相关值为 i 和 j 之间的简单路径所经过的所有边的权值的最小值。

有 Q 组询问,每组询问给出两个证书 k 和 v。对于每组询问,你需要输出所有与节点 v 相关值至少为 k 的节点个数(不包含 v 本身)。

思路

本题有弱化版(见题目背景),弱化版可以通过 DFS 求解。本题数据范围比弱化版高,暴力 DFS 会超时,所以需要考虑其他做法。

由于 Q 的范围大且难以做到 O(1) 或 O(\log N) 复杂度处理单次询问,考虑询问离线。将所有的询问离线存储,按照 k 值从大到小排序。将所有边按边权从大到小排序。处理询问时,可以将边权大于等于 k 的边逐步加入图中,则所求就是节点 v 所在连通块的大小减去 1。维护连通块大小可以用带权并查集解决。最后将答案存储起来并统一输出即可。

洛谷 P1197 - 星球大战

题意

一个无向无权图中有 n 个点(用 0 \sim n - 1 编号)和 m 条边。在过程中逐步删除一些点及与此点相连的边。求刚开始和每次删除后,图中的连通块个数。

思路

要求连通块个数,很容易想到并查集,然而并查集并不支持删边。于是我们可以反过来想,把从前往后删除边转化为从后往前添边。于是,我们可以将所有询问离线下来处理,从后往前逐渐加点添边,保存每次添边之后连通块的个数。

连通块个数可以用一个变量 cnt 维护,而不必每次都遍历一遍整个并查集。新增点时,cnt 增加 1;合并集合时,cnt 减少 1。

洛谷 P1196 - 银河英雄传说

题意

有 30000 艘战舰(以 1 \sim 30000 编号)排成 30000 列,第 i 号战舰在第 i 列。有以下两种指令:

  • M i j 代表将第 i 号战舰所在的整列整体接到第 j 号战舰所在的列的尾部;
  • C i j 代表询问 i 和 j 两战舰在同一列中相隔的战舰数量;如果 i 和 j 不在同一列,则结果为 -1。

有 T 条指令。处理这些指令。

思路

由于涉及到集合合并,很容易想到用并查集解决。为了能够求出同一列的两辆战舰间相隔的距离,我们额外维护两个属性:s_i 代表以 i 为根的集合的大小,d_i 代表 i 到集合根节点(列头)的距离。这个带权并查集很好维护。此后根据题意执行操作即可。

洛谷 P1955 - 程序自动分析

题意

有 t 个问题。每个问题包含若干个 x_i = x_j 或 x_i \neq x_j 的约束条件,判断这些约束条件是否能被同时满足。

思路

这道题和 HDU 6109 比较相像,但是 i, j 的范围过大。由于 n 并不大,所以考虑对约束条件中的 i,j 进行离散化。随后先处理相等关系,将所有的相等关系对应的集合合并。然后处理不等关系,如果发现 i 和 j 在一个集合里,则说明前面出现了 x_i = x_j 的情况,与 x_i \neq x_j 的约束条件矛盾,此时问题答案为否。如果所有不等关系都没有与前面的相等关系出现矛盾,则问题答案为是。

支持与分享

如果这篇文章对你有帮助,欢迎分享给更多人或者给予支持!

《并查集》一节习题笔记(三)
/2026/11/bing-cha-ji-yi-jie-xi-ti-bi-ji-san
作者
Tiger
发布于
2026-11-16
许可协议
CC BY-NC-SA 4.0