并查集：合并、查询与路径压缩

第一次碰到“并查集：合并、查询与路径压缩”，我以为把定义和代码记下来就算学会了。真正动手时才暴露出问题：路径压缩只有一行递归代码，我第一次看到时不明白它为什么不会破坏集合关系，也不知道它到底快在什么地方。这次重学我刻意放慢了速度，先看它为什么出现，再看规则怎样工作，最后才落到实现。

并查集（Union-Find）维护一组互不相交的集合，只关心两个问题：两个元素是否属于同一集合，以及怎样把两个集合合并。它不保存完整路径，也不提供有序遍历，却能高效处理动态连通性。

它从哪里来

并查集来自动态维护等价类和连通分量的需求。二十世纪六十年代以后，按大小合并与路径压缩逐步成为经典优化，Robert Tarjan 等人的分析进一步说明这些操作为何在长期使用中接近常数时间。

用父数组表示森林

并查集森林路径压缩前后对比图

图：find 访问过的节点直接连接代表元，按大小合并避免高树

parent[i] 指向节点 i 的父节点，根节点指向自己。两个元素的代表元相同，就属于同一集合。

public final class DisjointSet {
    private final int[] parent;
    private final int[] size;

    public DisjointSet(int n) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    public int find(int x) {
        int root = x;
        while (root != parent[root]) root = parent[root];
        while (x != root) {
            int next = parent[x];
            parent[x] = root;
            x = next;
        }
        return root;
    }

    public boolean union(int a, int b) {
        int ra = find(a);
        int rb = find(b);
        if (ra == rb) return false;
        if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
        parent[rb] = ra;
        size[ra] += size[rb];
        return true;
    }

    public boolean connected(int a, int b) {
        return find(a) == find(b);
    }
}

两个关键优化

路径压缩让 find 经过的节点直接指向根，后续查询更短。按大小或按秩合并则总让较小的树挂到较大的树下，避免产生长链。

两者同时使用时，连续操作的摊销复杂度为 O(α(n))，α 是增长极慢的逆阿克曼函数，在现实规模中几乎可以看作常数，但理论上不应直接写成严格 O(1)。

路径压缩也可以写成递归形式：

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

它简洁，但极端未优化树可能产生很深递归。迭代写法更容易避免调用栈风险。路径减半是另一种选择：遍历时让每个节点指向祖父，也能逐步压平路径。

按秩合并维护的是树高上界，按大小合并维护集合元素数。两者效果相近，但字段语义不同，不能把 rank 当成路径压缩后的真实高度。

典型应用

判断无向图中两个节点是否连通。
Kruskal 最小生成树中判断加入一条边是否形成环。
合并账号、好友群组或等价类。
网格中的岛屿连通与动态连通。

Kruskal 最小生成树

Kruskal 把边按权重升序处理。若一条边的两个端点已经连通，加入会形成环；否则加入结果并合并两个集合。

static long minimumSpanningTree(int vertices, java.util.List<Edge> edges) {
    edges.sort(java.util.Comparator.comparingInt(Edge::weight));
    DisjointSet sets = new DisjointSet(vertices);
    long total = 0;
    int selected = 0;
    for (Edge edge : edges) {
        if (!sets.union(edge.from(), edge.to())) continue;
        total += edge.weight();
        if (++selected == vertices - 1) break;
    }
    if (selected != vertices - 1) throw new IllegalStateException("graph disconnected");
    return total;
}

排序成本为 O(E log E)，并查集操作接近常数，因此整体主要由边排序决定。

统计集合信息

根节点可以维护集合大小、权重和或其他可合并聚合值。union 时只更新新根，查询时先 find 到根。若需要列出集合所有成员，仅靠 parent 数组并不高效，应额外维护成员表或离线扫描。

它不适合什么

普通并查集擅长合并，不擅长删除关系。一旦两个集合合并，想撤销需要回滚并查集、离线算法或其他动态图结构。它也不能告诉你两点之间的具体路径；如果业务需要路径，应保留图的边并使用 BFS/DFS。

回滚并查集通常禁用路径压缩，以便把每次 parent 和 size 修改压入历史栈并撤销；按大小合并仍能把高度控制在 O(log n)。这是一种典型取舍：放弃更激进的查询优化，换取可恢复状态。

易错点

find 没有检查索引范围。
合并时比较的是原节点大小，而不是两个根的大小。
路径压缩后忘记只有根节点的 size 才有意义。
在并发环境中无锁修改 parent，产生不可预测结构。

测试清单

初始每个元素只与自己连通。
重复 union 返回 false 且集合数不变。
按大小合并后小树根指向大树根。
长链查找后路径确实被压缩。
随机 union/connected 与朴素连通分量结果对照。
非法索引、空集合和超大规模初始化。

并查集最有启发性的地方是：它不试图维护完整答案，而只维护足以回答目标问题的最小状态。数据结构设计经常就是这种“用受控信息换取更低成本”的过程。