什么是并查集（Union-Find）？路径压缩和按秩合并是怎么优化的？

简化版

并查集是专门处理「动态连通性」的数据结构，支持两个操作：find(x) 找 x 所在集合的代表（根）、union(a,b) 合并两个集合。用「每个元素指向父节点、同一集合共用一个根」的森林实现。两个优化让它接近 O(1)：路径压缩（find 时把路径上的节点直接挂到根下）、按秩/按大小合并（把矮树挂到高树下，避免树变高）。用于判断连通、环检测、Kruskal、朋友圈。

详细版

class UnionFind {
    int[] parent, rank;
    UnionFind(int n) {
        parent = new int[n]; rank = new int[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 union(int a, int b) {           // 按秩合并
        int ra = find(a), rb = find(b);
        if (ra == rb) return;            // 已在同一集合
        if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; } // 保证 ra 更高
        parent[rb] = ra;                 // 矮的挂到高的下
        if (rank[ra] == rank[rb]) rank[ra]++;
    }
    boolean connected(int a, int b) { return find(a) == find(b); }
}

find：顺着 parent 往上找到根；路径压缩让沿途节点直接指向根。
union：找到两个根，把一个挂到另一个下面（按秩：矮的挂高的）。
connected：两者根相同即连通。

完整版教学

一、并查集解决什么问题

并查集专治「动态连通性」：不断地「把 a 和 b 归为一组」，并随时查询「a 和 b 是不是同一组」。比如社交网络里不断加好友、判断两人是否在同一朋友圈；网络节点不断连线、判断是否连通。这类「合并 + 查询归属」的问题，并查集用近乎常数的时间搞定，比每次 DFS 判连通高效得多。

二、核心思想：用森林表示集合

并查集把每个集合表示成一棵树，树根作为这个集合的代表。parent[x] 指向 x 的父节点，根节点的 parent 是自己。

判断两个元素是否同组：各自 find 到根，根相同就是一组。
合并两个集合：把一个集合的根挂到另一个集合的根下面。

初始时每个元素自成一棵单节点树（自己是自己的根）。

三、优化一：路径压缩

朴素 find 要顺着 parent 一路爬到根，如果树很高就慢。路径压缩：在 find 的过程中，把沿途经过的所有节点直接指向根。这样下次再 find 这些节点就一步到位。经过压缩，树会变得非常扁平（几乎所有节点直接挂在根下）。

四、优化二：按秩 / 按大小合并

如果合并时随意挂，可能把高树挂到矮树下，让树越来越高。按秩合并：总是把较矮的树挂到较高的树下面（rank 近似树高），这样合并后的树高不会轻易增加。按大小合并类似，把节点少的挂到节点多的下面。两者都是为了控制树高。

五、复杂度：接近 O(1)

单独用路径压缩、或单独用按秩合并，单次操作是 O(log n)。两个优化同时用，单次操作的均摊复杂度是 O(α(n))，其中 α 是反阿克曼函数——它增长极其缓慢，对任何现实规模的 n（哪怕宇宙原子数），α(n) 都 ≤ 4。所以并查集操作实际上就是常数时间。这是它高效的根本。

六、常见误区与追问

考点	正确口径
find	找到元素所在集合代表元
union	合并两个集合
路径压缩	find 时把路径节点直接挂到根
按秩合并	让小树挂到大树下

find(x):
  if parent[x] != x:
    parent[x] = find(parent[x])
  return parent[x]

并查集擅长动态连通性：只关心“是否在同一集合”，不关心具体路径长什么样。

误区：并查集能回答两点之间的具体路径。 它只维护连通分量代表，不能恢复路径；要路径需 DFS/BFS 或额外记录。
误区：union 直接随便挂不会影响复杂度。 长期随便挂可能形成高链，按秩或按大小合并能控制树高。
误区：路径压缩只优化当前节点。 递归回溯会把整条查找路径上的节点都直接连到根，后续查询更快。
追问：并查集适合哪些题？ 连通性、朋友圈、省份数量、无向图判环、Kruskal 最小生成树。
追问：复杂度为什么接近 O(1)？ 路径压缩加按秩合并后，均摊复杂度是反阿克曼函数级别，实际可视作常数。
追问：如何统计集合数量？ 初始化为 n，每次成功 union 两个不同集合时数量减一。

七、加强记忆

并查集（Union-Find）处理动态连通性：find 找集合代表（根）、union 合并、connected 判同组。用森林表示集合（parent 指向父、根代表集合）。两个优化：路径压缩（find 时把沿途节点直接挂到根、树变扁平）+ 按秩/按大小合并（矮树挂高树下、控制树高）。两者同用，单次操作近 O(α(n))≈O(1)（α 是反阿克曼函数，恒 ≤ 4）。应用：连通判断、环检测、Kruskal、朋友圈。

简化版

详细版