《并查集》一节习题笔记(二)
本文记录了作者学习罗勇军《算法竞赛》中《高级数据结构》一章《并查集》一节时,完成部分习题的笔记。
HDU 3635 - Dragon Balls
题意
有 n 个龙珠和 n 个城市,初始时第 i 个龙珠在第 i 个城市。需要处理 Q 个询问,分为两种:
T A B表示将 A 所在城市的所有龙珠转移到 B 城市(保证 A 和 B 原本不在一个城市);Q A表示查询 A 号龙珠所在城市编号 X、该城市龙珠总数 Y、该龙珠的转运次数 Z。
思路
使用带权并查集解决。除 p 数组外,额外维护两个并查集数组:siz_i 代表以 i 为根节点的子树的大小,dep_i 代表 i 相对于 i 的根节点的深度。
初始化所有 siz_i 为 1,dep_i 为 0。在合并 p_x 和 p_y 两个集合时,将 siz_{p_x} 累加到 siz_{p_y} 上,并将 dep_{p_x} 设为 1。查询时,分别输出 X = \operatorname{find}(A)、Y = siz_X、Z = dep_A 即可。
HDU 1856 - More is better
题意
有 10^7 个男生,从 1 到 10^7 编号。给出 n 个直接朋友对。定义两个人 A 和 B 是朋友,当且仅当 A 和 B 之间有直接朋友关系,或存在 C 与 A 和 B 均为朋友。希望从这些男生中挑出一群人,要求这群人两两之间都是朋友,求最多能挑选多少个男生。
思路
使用带权并查集解决。在普通并查集基础之上维护一个 siz 数组,siz_i 代表以 i 为根的子树的大小。按照题目意思对每个直接朋友对进行合并。在最后统计所有 siz_i 的最大值即可。
注意:对于非根节点 i,siz_i 是无意义的,所以不需要在 find 函数中压缩 siz_i,只需要在合并时累加即可。
HDU 1272 - 小希的迷宫
题意
给定一个无向图 G,判断其是否为一棵树(即连通且无环)。
思路
如果对于 G 中的两个点 u 和 v,它们之间有不止一条路径,那么这个图就不是树。使用并查集解决。如果两个点 u 和 v 在连新边之前已经连通(即在同一个集合里),那么它们之间有不止一条路径,答案为否。在所有边加完后,遍历所有的点,如果发现有超过一个集合,代表图不连通,答案同样为否。如果发现以上两种情况都不成立,答案为是。
注意本题特殊的输入格式需要处理。注意特判空树。
HDU 1325 - Is It A Tree?
题意
给定一个有向图,判断其是否是一棵树。
这里的树的定义与普遍定义有所不同:树是一个有向图;树存在一个根节点,没有边指向它;从根节点到任意其他节点都有唯一的一条有向路径。
思路
这题和上面的 HDU 1272 类似,区别在于无向图变成了有向图。使用并查集解决。大体思路和 HDU 1272 类似,但需要额外维护一个入度数组:依据题目中树的定义,除根节点之外,其他点的入度必须为 1,且根节点只有一个。
注意本题特殊的输入格式需要处理。注意本题输入并不是以 -1 -1 结尾,而是以两个负数结尾。
HDU 1198 - Farm Irrigation
题意
有一个 n \times m 的矩形田地,由 n \times m 个 1 \times 1 的方格组成。方格分为 11 种,有不同的水管排布方式,以 A ~ K 编号,如下图所示:

(图片来源:HDU OJ)
用字母矩阵的方式给出这个 n \times m 的矩形田地,求最少需要设立多少处水源才能灌溉到整个田地。
思路
首先考虑如何表示这 11 种方格,可以分为上、下、左、右四个方向是否连通来表示,用一个二维布尔数组存储。两个地块连通的条件是:
- 对 (i, j) 和 (i, j-1)(左侧方格),(i, j) 的左边和 (i, j-1) 的右边开口都为
true; - 对 (i, j) 和 (i-1, j)(上方方格),(i, j) 的上侧和 (i-1, j) 的下侧开口都为
true。
通过这两个规则对方格进行合并。注意将二维的点坐标 (i, j) 映射成一维的编号 i \times m + j 来维护并查集。最后求一遍集合的个数即可。
HDU 2586 - How far away?
题意
给定一个含有 n 个点的无向带权树 G,树中任意两个点都只有唯一的一条不重复经过点的简单路径,定义这条简单路径的长度为这两点之间的距离。有 m 个询问,每个询问包含两个整数 i 和 j,求每组询问中 i 和 j 的距离。
思路
本题是 LCA 的经典运用。维护一个 dep 数组,代表各点到 1 号点的距离。设 \operatorname{LCA}(i, j) 为 i 和 j 两点的最近公共祖先,则很容易知道点 i 和 j 之间的距离为:
将所有的询问离线下来,并使用 Tarjan 算法计算 LCA,再根据上面的公式求解。关于 Tarjan 算法,参见《算法竞赛》4.8.2 节。Tarjan 算法是 DFS 和并查集的巧妙运用。
HDU 6109 - 数据分割
题意
给定 L 个 x_i = x_j 或 x_i \neq x_j 的约束条件。每个约数条件以三个整数 a、b、e 给出:若 e = 1,代表 x_a = x_b;若 e = 0,代表 x_a \neq x_b。已知对于一组数据 [x, y],[x, y] 编号区间的约束条件是不可满足的,但 [x, y-1] 编号区间的约束条件是可满足的。求出这些组数据的个数及每组数据的长度。
思路
相等关系具有传递性,可以用并查集维护。不等关系不具有传递性,考虑用 set 维护,显式记录哪些关系是互斥的。开一个 set 数组(set<int>[])记为 s,集合 s_i 内存储的是与以 i 为根的集合互斥的集合的根节点。
首先考虑相等关系(e = 1)如何处理。设 a 和 b 所在集合的根节点分别为 r_a 和 r_b。若 r_a = r_b,代表二者此前就在一个集合里,此时无需再做处理。若 r_a \neq r_b,则需要合并两个集合:假设将集合 r_a 合并入集合 r_b,遍历 s_{r_a} 中的每一个元素 x,将 x \leftrightarrow r_a 的不等关系抹去,并添加 x \leftrightarrow r_b 的不等关系。注意这里要将小集合并入大集合,即要将 s_{r_a} 和 s_{r_b} 中含有元素较少的一个并入含有元素较多的一个,否则可能会超时。
接着考虑不等关系(e = 0)的处理。仍然设 a 和 b 所在集合的根节点分别为 r_a 和 r_b。若 r_a = r_b,代表此前有 x_a = x_b 的相等关系存在,产生互斥,结束这一组数据的计数并输出,清空所有数据结构开始下一组。若 r_a \neq r_b,即 x_a \neq x_b 与现有条件不冲突,则可以显式记录互斥关系,在 s_{r_a} 中插入 r_b,并在 s_{r_b} 中插入 r_a。
注意一些细节:由于本题数据规模较大,每次重置时可以只重置出现过的编号(可以用一个 vector 或 set 记录)。

