路径压缩：让并查集查找快如闪电

什么是路径压缩？

路径压缩是并查集（一种用来管理元素分组的数据结构）中最重要的优化技巧之一。它的目标是让查找元素所属的“组代表”（也叫根节点）变得飞快——无论链条有多长，经过一次路径压缩后，下次查找几乎只要一步就到。

想象一下你在学校参加运动会，每个班级都有一位“总班长”。如果你的班级结构是这样：你 → 小组长 → 副班长 → 班长（班长就是根）。你想找到班长，就得问小组长，小组长再问副班长，副班长再问班长。如果班级有100层，那问起来可太慢了。路径压缩就是：一旦你知道了班长是谁，就让你直接记住班长的名字，以后再也不需要中间人。甚至，连小组长、副班长也会一次性记住班长是谁。这样一来，整个班级就变成了“所有人都直接认识班长”的扁平结构。

从生活例子直观理解

例子1：找老师签名

假设学校要收作业，老师把任务下发给年级组长 → 年级组长下发给班主任 → 班主任下发给课代表 → 课代表下发给小组长 → 小组长再通知你。现在你想直接找老师签名，你得一级一级往上问。这很费时间。

如果使用路径压缩，在你第一次找到老师后，老师告诉你：“你下次直接来找我就行，不用再问别人了。”不仅如此，老师还会告诉年级组长、班主任、课代表、小组长：“以后你们大家都直接来找我！”从此以后，所有人找老师都只要一步。

例子2：家族家谱

你有一个庞大的家族树，曾祖父是根。你想知道自己的太爷爷是谁，需要先问爷爷，爷爷再问爸爸，爸爸问太爷爷。如果树很深，可能要问几十次。路径压缩的意思是：当你问到太爷爷后，你、你的爸爸、你的爷爷全部直接记住太爷爷，以后每个人再问都只需要一步。

路径压缩的核心原理

路径压缩通常和并查集的 find 操作一起实现。传统的 find(x) 只会沿着父节点往上找，直到找到根节点。路径压缩在此基础上增加了一个“后处理”步骤：

在找到根节点 root 后，将路径上所有经过的节点的父节点直接改为 root。
这样，下次再对这些节点调用 find，它们就会一步跳到根节点。

数学上，路径压缩让树的高度变得非常低（几乎为1或2），后续查找的平均时间复杂度接近常数 O(1)。

分步理解：从长链到星星

我们用一个数字例子来演示。假设并查集中有5个元素：1,2,3,4,5，它们的父节点关系如下（箭头表示父节点指向）：

压缩前：
1 → 2 → 3 → 4 → 5   (5是根)

现在我们要查找元素1的根。查找过程会经过1→2→3→4→5，最终找到根5。在找到根5后，路径压缩会做以下更新：

将 parent[1] 直接设为5
将 parent[2] 直接设为5
将 parent[3] 直接设为5
将 parent[4] 直接设为5
5的父节点还是5

压缩后的树变成了：

这就是一颗“星星”形状：所有非根节点直接指向根，高度只有2（根是自己的根，高度1）。从此，查找任何节点都只需要一步。

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

class DSU {
private:
    vector<int> parent;   // 父节点数组
public:
    DSU(int n) {
        parent.resize(n);
        for (int i = 0; i < n; i++) {
            parent[i] = i;   // 初始化：每个元素的父节点是自己（自己是根）
        }
    }

    // 查找操作：带路径压缩（递归写法）
    int find(int x) {
        if (parent[x] != x) {                     // 如果x不是根
            parent[x] = find(parent[x]);          // 递归找到根，并把当前节点的父节点设为根
        }
        return parent[x];                         // 返回根
    }

    // 合并两个元素所在的集合
    void unite(int x, int y) {
        int rootX = find(x);   // 先找到x的根
        int rootY = find(y);   // 再找到y的根
        if (rootX == rootY) return;   // 已经在同一个集合，不用合并
        parent[rootY] = rootX;   // 简单合并：把rootY的父节点设为rootX
    }

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

int main() {
    DSU dsu(100000);   // 创建10万个元素的并查集
    // 模拟一条长链的合并 (0-1, 1-2, 2-3, ...)
    for (int i = 0; i < 50000; i++) {
        dsu.unite(i, i + 1);
    }
    // 测试查询：经过路径压缩，查询非常快
    cout << "0和50000是否一组？ " << (dsu.same(0, 50000) ? "是" : "否") << endl;
    return 0;
}

注释说明：

parent 数组存储每个元素的父节点，初始化时 parent[i] = i。
find 函数中，如果 parent[x] != x，说明 x 不是根，则递归找到根，并在回溯时把 parent[x] 设为根。这一行 parent[x] = find(parent[x]) 就是路径压缩的核心。
unite 函数先找到两个元素的根，然后把一个根的父节点指向另一个根。这里没有采用按秩合并（即没有考虑树的大小），但路径压缩已经能大幅提升性能。

Python 实现（递归版）

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))   # 初始化，每个元素的父节点是自己

    def find(self, x):
        # 带路径压缩的查找：如果 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
        self.parent[root_y] = root_x   # 简单合并

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


if __name__ == "__main__":
    dsu = DSU(100000)
    for i in range(50000):
        dsu.union(i, i + 1)
    print("0和50000是否一组?", dsu.same(0, 50000))   # 输出 True

迭代版本（了解即可）

递归写法虽然简洁，但在某些语言或深度极大时可能栈溢出。迭代版本先找根，再压缩路径，更加安全。下面给出C++迭代版（已注释在原有代码中）：

int find(int x) {
    // 第一步：找到根
    int root = x;
    while (parent[root] != root) {
        root = parent[root];
    }
    // 第二步：压缩路径——把路径上所有节点的父节点设为根
    while (parent[x] != root) {
        int next = parent[x];  // 记录当前节点的父节点
        parent[x] = root;      // 直接将当前节点连到根
        x = next;              // 继续处理下一个节点
    }
    return root;
}

注意：迭代版本稍显繁琐，但不会递归，适合树上节点数巨大（比如上百万）且递归深度可能超过栈限制的情况。

新手常犯的错误

忘记在 find 中做路径压缩
有些人写 find 时只返回根，没有更新父节点。这样树永远不会变扁平，查找速度依然很慢。记住：必须在找到根后，把沿途所有节点的父节点都设成根。
递归写法中忘记 parent[x] = find(parent[x]) 这个赋值
如果只写 return find(parent[x])，虽然能返回根，但没有更新当前节点的父节点，路径压缩不起作用。
合并时没有先 find
直接写 parent[y] = x 或者 parent[x] = y 可能会导致错误，因为 x 和 y 本身可能不是根。必须先用 find 找到它们的根，然后合并根。
混淆了“路径压缩”和“按秩合并”
路径压缩是在查找时做的，合并时不做；按秩合并是在合并时根据树的大小或深度决定谁当根。两者独立但可以配合使用。初学者容易以为合并时也需要路径压缩，实际上合并时只需要更新根的父节点。
迭代版压缩时忘记循环条件
在迭代版中，while (parent[x] != root) 必须正确遍历从 x 到根路径上的所有节点。如果写错了条件，可能只压缩了当前节点而漏掉了中间节点。

完整可运行示例（含多个测试）

下面是一个更完整的测试，展示路径压缩的效果：先创建一个长链，然后进行大量查询，观察查询时间极短。

C++ 测试代码

#include <iostream>
#include <vector>
#include <chrono>   // 用于计时
using namespace std;

class DSU {
private:
    vector<int> parent;
public:
    DSU(int n) {
        parent.resize(n);
        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;
        parent[rootY] = rootX;
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }
};

int main() {
    int N = 1000000;  // 100万个元素
    DSU dsu(N);

    // 1. 链接成一条长链：0-1, 1-2, 2-3, ...
    for (int i = 0; i < N - 1; i++) {
        dsu.unite(i, i + 1);
    }

    // 2. 测试查询速度（第一次查询会触发路径压缩）
    auto start = chrono::steady_clock::now();
    bool res1 = dsu.same(0, N - 1);
    auto end = chrono::steady_clock::now();
    cout << "第一次查询 0 和 " << N - 1 << " 是否一组: " << (res1 ? "是" : "否") << endl;
    cout << "耗时: " << chrono::duration_cast<chrono::microseconds>(end - start).count() << " 微秒" << endl;

    // 3. 再次查询（已经路径压缩，瞬间完成）
    start = chrono::steady_clock::now();
    bool res2 = dsu.same(0, N - 1);
    end = chrono::steady_clock::now();
    cout << "第二次查询 0 和 " << N - 1 << " 是否一组: " << (res2 ? "是" : "否") << endl;
    cout << "耗时: " << chrono::duration_cast<chrono::microseconds>(end - start).count() << " 微秒" << endl;

    // 4. 随机查询大量节点，观察总体时间
    start = chrono::steady_clock::now();
    for (int i = 0; i < 100000; i++) {
        dsu.same(i, i + 100);
    }
    end = chrono::steady_clock::now();
    cout << "10万次随机查询总耗时: " 
         << chrono::duration_cast<chrono::milliseconds>(end - start).count() 
         << " 毫秒" << endl;

    return 0;
}

预期输出（时间因机器而异）：

第一次查询 0 和 999999 是否一组: 是
耗时: 大约 几微秒 到 几十微秒
第二次查询 0 和 999999 是否一组: 是
耗时: 不到 1 微秒
10万次随机查询总耗时: 大约 0~10 毫秒

Python 测试代码

import time

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))

    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):
        rx = self.find(x)
        ry = self.find(y)
        if rx == ry:
            return
        self.parent[ry] = rx

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


N = 1000000
dsu = DSU(N)
for i in range(N - 1):
    dsu.union(i, i + 1)

# 测试
start = time.time()
res1 = dsu.same(0, N - 1)
end = time.time()
print(f"第一次查询: {res1}, 耗时 {end - start:.6f} 秒")

start = time.time()
res2 = dsu.same(0, N - 1)
end = time.time()
print(f"第二次查询: {res2}, 耗时 {end - start:.6f} 秒")

start = time.time()
for i in range(100000):
    dsu.same(i, i + 100)
end = time.time()
print(f"10万次查询总耗时: {end - start:.6f} 秒")

总结要点

路径压缩的作用：让树变得扁平，查找速度几乎常数级。
实现方式：在 find 函数中，找到根后，将路径上所有节点的父节点直接设为根。递归写法一行搞定。
时间复杂度：单独使用路径压缩，均摊复杂度接近 O(log n)；配合按秩合并后，接近 O(α(n))，其中 α(n) 是反阿克曼函数，增长极慢，对于所有实际数据可视为常数。
常见错误：
- 忘记在 find 中更新父节点
- 合并前没有 find 获取根
- 递归深度过大导致栈溢出（可用迭代版避免）
使用场景：凡是使用并查集的地方，都应该启用路径压缩，它是标准优化。

路径压缩优化