39
0

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

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

POJ 2524 - Ubiquitous Religions

题意

有 n 个元素,给出 m 对元素属于同一集合,求最多有多少个集合。

思路

使用并查集解决。将每对元素合并到一个集合内,最终产生的集合数即为答案。要求集合数,判断 p_i = i 的个数即可。

POJ 1611 - The Suspects

题意

有 n 个元素用 0 \sim n - 1 编号,给出 m 组元素,每组若干个元素属于同一集合,求与 0 号元素属于同一集合的元素个数(0 号元素也算)。

思路

使用并查集解决。将每组的所有元素合并到一个集合中,最终遍历所有元素,\operatorname{find}(i) = \operatorname{find}(0) 的个数即为答案。

POJ 1703 - Find them, Catch them

题意

有 n 个元素和两个非空集合 A 和 B,给出 m 条消息,分为两种:

  • D x y 表示 x 和 y 不属于同一集合;
  • A x y 表示询问 x 和 y 是否属于同一集合。

对于每个第二类 A 消息,给出下列三种反馈中的一种:

  • In the same gang. 表示 x 和 y 在同一集合;
  • In different gangs. 表示 x 和 y 属于不同集合;
  • Not sure yet. 表示还不能确定 x 和 y 是否属于同一集合。

思路

使用扩展域并查集解决。对于 1 \leq x \leq n,x 表示 x 属于 A 的假设,x + n 表示 x 属于 B 的假设。

对于每个 D 消息:如果 x 属于 A,那么 y 就属于 B,合并 x 和 y + n;如果 x 属于 B,那么 y 就属于 A,合并 x + n 和 y。

对于每个 A 消息:如果 x 和 y 在同一集合,说明 x 和 y 同属一个集合;如果 x 和 y + n 在同一集合,说明 x 和 y 在不同集合;如果上面两种情况都不成立,说明还不能确定 x 和 y 的关系。

代码比较简单,注意数组要开到两倍,初始化并查集时要初始化到 2n。

POJ 2236 - Wireless Network

题意

平面上有 n 个点,第 i 个点的坐标为 (x_i, y_i),初始状态都未激活。每个激活点只能与和它的欧几里得距离不超过 d 且也激活的点连线。我们称两个激活的点 A 和 B 连通,当且仅当 A 和 B 之间有直接连线,或存在激活的点 C 与点 A 和 B 都连通。未激活的点不与其他任何点连通。

现在给出若干操作。操作分为以下两种:

  • O p 表示使点 p 变为激活状态;
  • S p q 表示判断点 p 和 q 是否连通。

对于每个第二类 S 操作,给出下面两种反馈中的一种:

  • SUCCESS 表示点 p 和 q 连通;
  • FAIL 表示点 p 和 q 不连通。

思路

使用并查集解决,首先要维护一个布尔类型的 v 数组,v_i 代表第 i 个点是否被激活。

对于每个 O 操作,将 v_p 设为 true 后遍历 v 数组,找出所有激活的点并判断其是否与 p 有连线,如有,则合并两个集合。

对于每个 S 操作,判断 p 和 q 是否属于同一集合即可。

这里注意,为避免浮点数精度误差,判断两点 i 和 j 是否有直接连线时,只需要判断 (x_i - x_j)^2 + (y_i - y_j)^2 \leq d^2 即可,无需开平方。

POJ 2492 - A Bug's Life

题意

对于每组测试数据,有 n 个元素和两个集合。有如下假设:只有属于不同集合的元素之间才会发生互动。给出所有互动的两个元素 x 和 y,判断是否有互动推翻了假设。

思路

和上面的 POJ 1703 类似,使用扩展域并查集解决。对于一次互动的两个元素 x 和 y,如果此前已经有 \operatorname{find}(x) = \operatorname{find}(y) 成立,则说明 x 和 y 属于同一集合,与假设不符;否则,合并 x 和 y + n、x + n 和 y。使用一个布尔型的 f 变量来记录结果。

这里可以有一个小优化,如果此前已经判断 f 为 true 了,那么下面的互动只需要输入,不需要再进一步判断。

POJ 1988 - Cube Stacking

题意

有 n 个元素和 n 个栈。初始时,第 i 个栈只有元素 i。有 P 次操作,操作分为两种:

  • 移动操作 M x y:将包含 x 的整个栈移到包含 y 的整个栈的上面;
  • 计数操作 C x:查询在包含 x 的栈中,x 的下方有多少个元素。

题目中不给出 n 的值。对于每个计数操作,输出一行一个整数代表这次计数操作的查询结果。

思路

使用带权并查集解决。维护三个数组:p_i 代表第 i 个元素所在集合的根节点,siz_i 代表以第 i 个元素为根的集合的大小,u_i 代表第 i 个元素到根节点的距离,也就是 i 下方有多少个元素。

在合并的时候,分别找到 p_x 和 p_y,这里我们维护的根节点是栈中最下方的元素,所以可以直接把 p_x 接到整个 y 所在集合的上方。在查找时,需要路径压缩,累加父节点到根的距离。

注意:在每次计数操作查询前,必须先执行一遍 find 进行路径压缩更新数据。

支持与分享

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

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