并查集的按秩合并与启发式合并：让集合合并又快又稳

为什么需要按秩合并？

并查集是一种用来管理元素分组的数据结构，它支持两种操作：查找某个元素属于哪个组，以及合并两个组。如果没有优化，合并时随意连来连去，可能会让一组变得很长——就像一条链子，查找时得一步一步走到底，效率很低。

想象一下：你们班上要组建几个兴趣小组，每个小组有一个“组长”。如果某天两个小组合并，新组长怎么选？最笨的方法是让一个组长的“上司”变成另一个组的组长，但这样会导致层级变多。比如A组有50人，组长是阿强；B组只有2人，组长是小华。如果让阿强当小华的下属（阿强指向小华），那么A组50人每次要找组长，都得先找到阿强，再找到小华，多走一步。反过来，让小华成为阿强的下属，则A组人员找组长一步到位，只有B组那2人需要多走一步。显然，把小树挂到大树上，让新增的路径尽可能短，这就是“按秩合并”的核心思想。

按秩合并就是要避免树变得太高，让每次查找和合并操作都保持在接近常数的速度。当它和路径压缩配合使用时，并查集就达到了近乎完美的效率——单次操作的时间复杂度可以看作常数（反阿克曼函数）。

生活中的例子：合并小组，怎么选组长？

让我们用更具体的场景来理解。你所在的学校组织社团活动，每个社团有一名“社长”。当两个社团决定合并时，需要确定新的社长。有两个社团：

书法社：有50名同学，社长是阿强。
棋艺社：有2名同学，社长是小华。

现在要合并成一个“书法棋艺社”。有两种合并方式：

小社团挂到大社团下：让小华（棋艺社社长）变成阿强的下属（即小华的上级是阿强）。这时，原本棋艺社的2名同学要找新社长，需要先找小华，再找阿强（2步）；而书法社的50名同学直接找阿强（1步）。整体平均步数很少。
大社团挂到小社团下：让阿强变成小华的下属（即阿强的上级是小华）。这样书法社的50名同学都得先找阿强，再找小华（2步）；棋艺社的2名同学则要找小华（1步）。平均步数明显变大，而且随着大社团规模增大，劣势更明显。

所以聪明的做法是把小树（小社团）合并到大树（大社团），这样树的深度增长最慢。在实际编程中，“秩”可以是树的高度，也可以是集合的大小。按高度合并时，我们让矮的树指向高的树；按大小合并时，让元素少的集合指向元素多的集合。两种做法效果相近，都能保证树的高度不超过 O(log n)。

按秩合并的原理：用“秩”来决策

在并查集的实现中，每个节点都有一个“父指针”指向它的上级，根节点的父指针指向自己。秩是一个记录在根节点上的值，它近似表示以该节点为根的树的高度（或节点个数）。我们只需要维护每个根节点的秩，非根节点的秩不重要，因为路径压缩会改变树的结构。

秩的定义

通常初始时，每个节点都是独立的树，秩为 0（如果按高度定义）或 1（如果按节点数定义）。
合并时，我们比较两个根节点的秩：
- 如果秩不同，把秩较小的根指向秩较大的根，秩不变（因为矮树挂到高树下，新树的高度等于高树的高度）。
- 如果秩相等，可以把任意一个根指向另一个，但被指向的根的秩需要加 1（因为两棵高度相同的树合并，新树高度增加 1）。

为什么秩可以近似而不精确？

由于路径压缩（查找时直接把节点挂到根下）会降低树的高度，如果每次修改都更新秩，会很麻烦。实际上，我们只把秩当作一个“历史估计值”来使用，即使路径压缩后树的高度变小了，秩也可能比实际高度大。这并不影响合并时的决策——因为按秩合并的目的只是在合并时防止树过分增高，而不是精确维护高度。实践证明，这种近似完全有效。

举个例子

假设有四个节点：0、1、2、3，各自独立。

合并 0 和 1：两棵树高度都为 0（秩相等）。让 1 指向 0，然后将 0 的秩加 1，变成 1。现在树：0（秩1）→ 1（秩0）。
合并 2 和 3：同样，让 3 指向 2，2 的秩变为 1。树：2（秩1）→ 3（秩0）。
合并 0 和 2：两棵树的根分别是 0（秩1）和 2（秩1），相等。让 2 指向 0，然后 0 的秩加 1，变成 2。现在整棵树：0（秩2）→ 1，0 → 2 → 3。树的高度为 2（从 3 到 0 需要两步），而秩记录为 2，恰好匹配（近似）。

如果不按秩合并，比如每次都把大树的根指向小树的根，那么树可能很快退化成一条链，高度达到 n，查找效率就变成了 O(n)。

按大小合并：另一种直观的启发式

除了按高度，还可以按集合的大小来合并。这种办法更直观：谁的人多，谁就当老大。合并时，将元素少的集合的根指向元素多的集合的根，并更新大小。这样做同样能保证树的高度不超过 O(log n)，因为每次合并后，新集合的大小至少是原来较小集合的两倍（类似二分）。

例如，还是刚才的书法社（50人）和棋艺社（2人），按大小合并且让小社团挂到大社团下，结果和按高度合并一样。按大小合并的优势在于：实现简单，不需要处理秩相等的情况（只需比较大小，大小不同就直接挂；如果大小相等，随便挂一个，大小相加即可）。

按大小合并的代码示意（C++）

vector<int> parent;
vector<int> size;   // 存储每个根节点的集合大小，初始为1

void unite(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX == rootY) return;
    // 确保 rootX 是较大的集合
    if (size[rootX] < size[rootY]) {
        swap(rootX, rootY);
    }
    parent[rootY] = rootX;              // 小根指向大根
    size[rootX] += size[rootY];         // 更新大集合的大小
}

Python 实现类似：

def union(self, x, y):
    root_x = self.find(x)
    root_y = self.find(y)
    if root_x == root_y:
        return
    if self.size[root_x] < self.size[root_y]:
        root_x, root_y = root_y, root_x
    self.parent[root_y] = root_x
    self.size[root_x] += self.size[root_y]

注意：按大小合并时，size 只对根节点有意义，非根节点的 size 值不会被用到。

完整代码实现（C++ 和 Python）

下面给出包含了路径压缩和按秩合并的完整并查集实现。路径压缩会在查找时把沿途所有节点直接连接到根上，进一步压扁树结构。

C++ 完整代码

#include <iostream>
#include <vector>
using namespace std;

class DSU {
private:
    vector<int> parent;   // 父指针数组
    vector<int> rank;     // 秩数组，记录树的高度（估计值）
public:
    // 构造函数：初始化 n 个节点，每个节点自成一个集合
    DSU(int n) {
        parent.resize(n);
        rank.resize(n, 0);          // 初始秩为0
        for (int i = 0; i < n; i++) {
            parent[i] = i;          // 每个节点指向自己
        }
    }

    // 查找：带路径压缩
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);   // 递归路径压缩
        }
        return parent[x];
    }

    // 按秩合并
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) return;

        // 将秩小的树挂到秩大的树下
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;          // X的根指向Y的根
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;          // Y的根指向X的根
        } else {
            // 秩相等，可以随意挂，但被挂的树秩需要+1
            parent[rootY] = rootX;
            rank[rootX]++;                  // 新树高度增加1
        }
    }

    // 判断两个元素是否在同一集合中
    bool same(int x, int y) {
        return find(x) == find(y);
    }
};

int main() {
    DSU dsu(10);          // 创建10个元素的并查集
    dsu.unite(0, 1);      // 合并0和1
    dsu.unite(2, 3);      // 合并2和3
    dsu.unite(0, 2);      // 合并两棵高度为1的树，rank[0]会变为1
    cout << "0和3是否一组？ " << (dsu.same(0, 3) ? "是" : "否") << endl;  // 输出：是
    return 0;
}

Python 完整代码

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))   # 父指针数组，初始指向自己
        self.rank = [0] * n            # 秩数组，初始为0

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 路径压缩
        return self.parent[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return
        # 按秩合并
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)


if __name__ == "__main__":
    dsu = DSU(10)
    dsu.union(0, 1)
    dsu.union(2, 3)
    dsu.union(0, 2)
    print(dsu.same(0, 3))   # 输出 True

常见错误与注意事项

忘记初始化父指针和秩：每个节点的父指针必须指向自己（parent[i] = i），秩初始为0（或1）。如果不初始化，程序可能崩溃或出现死循环。
合并时使用了非根节点的秩：秩只对根节点有意义。一定要先找到根节点（rootX = find(x)），再比较根的秩。不要直接用 x 或 y 的秩。
秩相等时忘记加 1：当两棵树高度相等，合并后新树高度会加 1。如果漏掉加 1，后面的合并可能无法正确反映树的高度，影响效率（虽然不会错，但可能退化）。
在路径压缩中混用秩更新：路径压缩会改变树的高度，但秩不需要更新。不要试图在 find 中同时更新秩，因为秩只是近似值，保持简单即可。
混淆按秩合并与按大小合并：按大小合并时，比较的是集合大小，不是高度。两者不能混用数组（比如不能把一个 size 数组当作秩来比较）。如果坚持使用按高度，要注意秩的初始值和更新规则。
递归路径压缩可能导致栈溢出：当树很深（比如 n=10^5）时，递归调用 find 可能消耗大量栈空间。如果担心，可以用迭代写法：

int find(int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];  // 隔代压缩
        x = parent[x];
    }
    return x;
}

迭代版本也能实现路径压缩，只是压缩不完全，但效果也很好。

按秩合并与启发式合并