当前没有测试数据。

本周课后复习：并查集

选择题直接写在代码区提交 编程题点击链接跳转到对应的题目去做

• 覆盖内容：并查集（合并集合、查询是否在同一集合、路径压缩）

• 满分：32 分（选择题 2×3 + 判断题 2×3 + 编程题 10×2）

---

一、每周解题技巧复习

本周主题：并查集 —— 把「一家人」用一个数组管起来。

技巧 1：用 fa 数组表示「我的爸爸是谁」

• 一开始每个人都是自己家族的根：fa[i] = i。

• 两个人是亲戚（要合并），就把一个人的根连到另一个人的根上。

• 小口诀：自己的根是自己，合并就认一个根。

int fa[MAXN];
for (int i = 1; i <= n; i++) fa[i] = i;   // 初始化

技巧 2：findRoot —— 沿着爸爸一直往上找到根

• findRoot(x) 返回 x 所在家族的根。

• 找到根之后，再把路径上遇到的点直接连到根上（路径压缩），下次找就很快。

• 小口诀：找根一路向上走，顺手把路压短。

int findRoot(int x) {
    if (fa[x] != x) fa[x] = findRoot(fa[x]);  // 路径压缩
    return fa[x];
}

技巧 3：mergeSet —— 合并两个家族

• 先分别找 $a$、$b$ 的根。

• 只有根不同（真的两个家族）才需要改 fa；根相同说明本来就在一家，什么都不做。

• 小口诀：根不同才合并，根相同就跳过。

void mergeSet(int a, int b) {
    int ra = findRoot(a);
    int rb = findRoot(b);
    if (ra != rb) fa[ra] = rb;
}

技巧 4：判断两人是不是一家人

• 两个人是一家人 $\iff$ 他们的根相同：findRoot(a) == findRoot(b)。

• 小口诀：同根即同家。

if (findRoot(a) == findRoot(b)) cout << "Yes";
else cout << "No";

技巧 5：用计数器记录「一共有几个家族」

• 一开始有 $n$ 个家族。

• 每次真正合并（根不同）成功，家族数就减 1；无效合并不减。

• 小口诀：合并一次，家族少一个。

int cnt = n;
// 合并 a, b
if (ra != rb) { fa[ra] = rb; cnt--; }   // 只有真合并才减

---

二、选择题（每题 2 分，共 6 分）

第 1 题

1. 并查集最擅长解决下面哪一类问题？（ ）。

A. 求两点之间的最短路径

B. 把元素分成若干集合，能快速合并两个集合、判断两个元素是否在同一集合

C. 给数组从小到大排序

D. 求一个数的质因数分解

第 2 题

1. 关于 findRoot（查找）函数里的「路径压缩」，下列说法正确的是？（ ）。

A. 路径压缩会让树变得更高

B. 路径压缩会改变每个元素属于哪一个集合

C. 路径压缩把查找路径上的点直接连到根，让以后的查找更快

D. 路径压缩会把两个集合合并成一个

第 3 题

1. 用 fa 数组实现并查集，初始化时应该把每个 fa[i] 设成什么？（ ）。

A. fa[i] = 0

B. fa[i] = i（每个元素自己就是一个集合的根）

C. fa[i] = i + 1

D. fa[i] = n

---

三、判断题（每题 2 分，共 6 分）

第 4 题

1. 并查集初始化后，每个元素各自独立成一个集合，此时 $fa[i] = i$。（ ）

第 5 题

1. 合并两个集合时，即使两个元素本来已经在同一个集合里，也必须修改 fa 数组。（ ）

第 6 题

1. 判断两个元素是否属于同一集合，只需比较它们的根 findRoot(a) 和 findRoot(b) 是否相等。（ ）

---

四、编程题（每题 10 分，共 20 分）

https://cpp.zhimabc.top/p/4986

https://cpp.zhimabc.top/p/4985

---