第 10 章：并查集 (Union-Find / Disjoint Set Union)

10.1 核心概念：找老大

想象一个江湖。一开始，有 $N$ 个侠客，每个人都自立门派，自己是自己的掌门。并查集主要处理两件事：

合并 (Union)：侠客 A 和侠客 B 打了一架，A 输了，A 就拜 B 为老大。从此 A 的门派归入 B 的门派。
查询 (Find)：我们要判断侠客 X 和侠客 Y 是不是一家人？很简单，问问 X 的最终大老板是谁，再问问 Y 的最终大老板是谁。如果是同一个人，那他们就是一家人。

10.2 数据结构实现

我们需要一个数组 fa[N] (father)。

fa[i] = k 表示： $i$ 的直接上级是 $k$ 。
如果 fa[i] == i，说明 $i$ 就是这个帮派的最高掌门人（根节点）。

10.2.1 初始化

一开始，每个人都是自己的老大。

int fa[1005];
 
void init(int n) {
    for (int i = 1; i <= n; i++)
        fa[i] = i; // 自己管自己
}

10.2.2 查询 (Find) 与路径压缩

这是并查集的灵魂。如果不优化，查找老板可能需要一级级向上问（像链表一样），最坏是 $O(N)$ 。

路径压缩 (Path Compression)：当小弟 $x$ 第一次去找大老板的时候，找到之后，直接把 $x$ 的上级改为大老板。下次 $x$ 再想找老板，一步就能找到。

// 查找 x 的祖宗（带路径压缩）
int find(int x) {
    if (fa[x] == x) 
        return x; // 找到祖宗了
    else {
        // 递归找祖宗，并且把沿途所有人的上级直接改成祖宗
        fa[x] = find(fa[x]); 
        return fa[x];
    }
}
// 极简一行写法：
// return fa[x] == x ? x : fa[x] = find(fa[x]);

10.2.3 合并 (Union)

要把 $x$ 和 $y$ 两个帮派合并。只需要让 $x$ 的祖宗 拜 $y$ 的祖宗 为老大即可。

void merge(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    
    if (rootX != rootY) {
        fa[rootX] = rootY; // 让 X 的老大归顺 Y 的老大
    }
}

10.3 复杂度分析

虽然看起来有递归，但因为路径压缩的存在，只要查询过一次，路径就被拍扁了。加上另一种优化策略“按秩合并”（虽不常写，但了解即可），并查集的时间复杂度是 $O(\alpha(N))$ 。

$\alpha(N)$ 是阿克曼函数的反函数。虽然它在增长，但增长极慢。对于宇宙中所有的粒子总数 $N$ ， $\alpha(N)$ 甚至不超过 4。 所以，你可以认为并查集的操作是 $O(1)$ 的。

10.4 进阶应用

10.4.1 连通块数量

问题：图中有 $N$ 个点， $M$ 条边，问图中有几个独立的连通块？解法：每输入一条边 $(u, v)$ ，就执行 merge(u, v)。最后统计 fa[i] == i 的个数，就是连通块的数量。

10.4.2 种类并查集（敌人的敌人是朋友）

场景：P1525 [NOIP2010 提高组] 关押罪犯 如果你知道 A 和 B 是敌人，B 和 C 是敌人，那么 A 和 C 应该在同一个监狱（朋友）。技巧：开两倍大小的数组 fa[2*N]。

$1 \sim N$ 表示自己。
$N+1 \sim 2N$ 表示“我的敌人”。
如果 A 和 B 是敌人，就合并 merge(A, B + N) 和 merge(B, A + N)。

10.4.3 最小生成树 (Kruskal 算法)

这将在图论部分详细讲，但核心就是：把边按权值排序，从小到大选边。如果这条边的两个端点不在同一个集合（用 find 判断），就选这条边，并 merge 它们。

🧠 本章小结与练习

并查集是处理“不相交集合”合并问题的神器。它的代码极短，极易实现，是考场上的拿分点。

练习作业：

P1551 亲戚 (洛谷)：并查集最基础的模板题。
P3367 【模板】并查集：去验证一下你的模板能不能通过 $N=10^4$ 的数据。
LeetCode 547. 省份数量：求连通分量的个数。

到目前为止，我们处理的数据结构（数组、栈、队列、集合）大多是线性的。从下一章开始，我们要进入图论 (Graph Theory) 的世界。那是一个由节点和边构成的复杂网络。