原始题目

下面并查集代码的横线处应该填什么？

int parent[N];

int find(int x) {
    if (parent[x] != x) {
        parent[x] = ___;
    }
    return parent[x];
}

• A. find(parent[x])
• B. parent[find(x)]
• C. x
• D. parent[x]

答案：A（find(parent[x])）

这就是并查集查找操作的路径压缩标准写法：

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);   // 递归找到根，顺手把 x 直接挂到根上
    }
    return parent[x];
}

图解：压缩前 vs 压缩后

原理：parent[x] != x 说明 x 不是根。递归 find(parent[x]) 一路找到根，返回时把每个经过的节点直接改指向根——下次再查这条链，一步到位。

逐项排除

配套：union（按秩合并）

void unite(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry) return;
    if (rk[rx] < rk[ry]) swap(rx, ry);
    parent[ry] = rx;                       // 矮树挂到高树下
    if (rk[rx] == rk[ry]) rk[rx]++;
}

两个优化叠加才达到最优：

\(\alpha(n)\) 是阿克曼反函数，实际应用中不超过 4，可视为常数。

易错细节

1. 初始化不能漏：for (int i = 0; i < n; i++) parent[i] = i;，每个点先自成一树。
2. 判同集合用 find(a) == find(b)，不能写 parent[a] == parent[b]——压缩前 parent 不一定是根。
3. 合并只改根的父亲：parent[ry] = rx，不要直接改 parent[x] 或 parent[y]。
4. 递归版 find 在极端深链（未压缩时）可能栈溢出，工程上可写非递归版：

int find(int x) {
    int r = x;
    while (parent[r] != r) r = parent[r];   // 先找根
    while (parent[x] != x) {                // 再统一压缩
        int t = parent[x];
        parent[x] = r;
        x = t;
    }
    return r;
}

考点总结（CSP-J/S 初赛、程序填空）

1. 填空见到 parent[x] != x → 紧跟 parent[x] = find(parent[x]);，这就是路径压缩。
2. 路径压缩 + 按秩合并 = \(O(\alpha(n))\)，只做其一是 \(O(\log n)\)。
3. 判连通 / 最小生成树 Kruskal 都靠它，核心操作只有 find 和 unite 两个。
4. 常见坑：忘记初始化、用 parent[ 直接比较、合并时没先 find。

思考题

如果只写路径压缩、不做按秩合并（union 时随便挂），单次操作的最坏均摊复杂度是多少？