并查集（Union-Find）是什么？路径压缩和按秩合并为什么有效？

直接回答：并查集是维护「不相交集合分组」的数据结构，支持两个操作：find(x) 返回 x 所在集合的代表元（根），union(x, y) 合并两者所在集合。用 parent 数组存父指针、根指向自己。两个优化：路径压缩（find 时把沿途节点直接挂到根上，树变扁平）和按秩合并（union 时把小树挂到大树下，抑制树高）。两者合用后单次操作摊还复杂度约 O(α(n))，α 是反阿克曼函数，实际应用视为常数。

展开解析：正确性要点：find 的压缩不改变集合划分（只改指向），按秩合并保证不压缩时树高也 ≤ log n——单独一个优化都能得到不错的上界，合起来才是近常数。典型应用：Kruskal 最小生成树、无向图判环（union 时发现同根即有环）、连通分量计数（岛屿数量的另一种解法）、等式方程的可满足性（先合并等式再检查矛盾）。易错点：union 要先 find 出根再合并根，而不是直接改 x、y 的父指针。追问方向：带权并查集（维护到根的偏移量，处理「距离/倍数关系」类约束，如食物链问题）、可撤销并查集（只按秩合并不压缩，配合回滚栈支持 undo）。

示例：

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # 路径压缩（隔代）
            x = self.parent[x]
        return x
    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        return True