并查集：原理与 Java 实现

并查集（Union-Find / Disjoint Set Union，DSU）是图论里投入产出比最高的数据结构：不到二十行代码，专门回答一类问题——两个元素是否连通？并且连通关系会动态变化（不断合并）。

一、它解决什么问题

设想两个需求场景：

社交网络里，不断有人加好友，随时要回答"小明和大明是否在同一个朋友圈"；
往一张图里一条边一条边地加，每加一条边都要立刻判断"这两个点是否已经连通"。

用 DFS 每次查询都重跑一遍 O(n+m)，边一多就崩了。并查集把连通性维护成森林：同一个连通块里的节点挂在同一棵树下，共享一个根节点。判断连通 = 判断根是否相同；合并连通块 = 把一棵树挂到另一棵树下。单次操作摊还下来接近 O(1)。

两个核心动词：

find(x)：找 x 所在树的根节点（根相同 ⇔ 连通）；
union(x, y)：把 x 和 y 所在的两棵树合并成一棵。

二、朴素实现

用数组 father[i] 存 i 的父节点，根节点指向自己：

int[] father;
 
public void init(int n) {
    father = new int[n];
    for (int i = 0; i < n; i++) father[i] = i;   // 各自为根
}
 
// 朴素 find：一路向上找到根
public int find(int x) {
    while (father[x] != x) x = father[x];
    return x;
}
 
public void union(int x, int y) {
    int rootX = find(x), rootY = find(y);
    if (rootX == rootY) return;                  // 本来就连通
    father[rootX] = rootY;                       // 一棵树挂到另一棵下
}

朴素版的问题：合并太随意，树可能退化成链（每次都把大树挂到小树叶子下面），find 最坏 O(n)。两大优化就是为了让树永远保持矮胖。

三、两大优化

优化一：路径压缩（find 时拍平）

find 走到根之后，顺手把沿途所有节点直接挂到根下——下次再查就是一步到位：

// 递归写法：把 x 的父节点直接改成根，整条链被拍平
public int find(int x) {
    if (father[x] != x) {
        father[x] = find(father[x]);    // 递归返回的就是根
    }
    return father[x];
}

压缩前：0→1→2→3→root          压缩后：0→root
                                     1→root
                                     2→root
                                     3→root

优化二：按秩合并（union 时挑挂的方向）

合并时把矮的树挂到高的树下（按 rank），或把小的树挂到大的树下（按 size，再维护一个计数的数组）。这样合并出的树高度受控：

int[] rank;   // 初始化为 0，rank[i] 近似树高
 
public void union(int x, int y) {
    int rootX = find(x), rootY = find(y);
    if (rootX == rootY) return;
    if (rank[rootX] < rank[rootY]) {
        father[rootX] = rootY;          // 矮挂高
    } else if (rank[rootX] > rank[rootY]) {
        father[rootY] = rootX;
    } else {
        father[rootY] = rootX;          // 等高时任挂一边，高的那棵 rank+1
        rank[rootX]++;
    }
}

两者任选其一已能保证单次操作 O(logn)，两个都上则摊还复杂度接近 O(1)（精确值是反阿克曼函数 α(n)，可视为常数）。路径压缩实现最简单，面试手写推荐它 + 一个方向随意的 union；工程上两者并用最稳。

四、完整 Java 模板（数组版）

把上面组装成一份可直接抄进题解的模板：

class UnionFind {
    private final int[] father;
    private int count;                       // 连通块个数（按需保留）
 
    public UnionFind(int n) {
        father = new int[n];
        count = n;
        for (int i = 0; i < n; i++) father[i] = i;
    }
 
    public int find(int x) {                 // 路径压缩
        if (father[x] != x) {
            father[x] = find(father[x]);
        }
        return father[x];
    }
 
    public void union(int x, int y) {        // 默认随机方向 + 维护 count
        int rootX = find(x), rootY = find(y);
        if (rootX == rootY) return;
        father[rootX] = rootY;
        count--;                             // 合并成功，连通块 -1
    }
 
    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }
 
    public int getCount() { return count; }
}

五、实战三例

547. 省份数量

n 个城市，isConnected[i][j] = 1 表示直接相连，省份是城市的极大连通块。把每个矩阵里的 1 当成一次 union，最后数有几个根——直接用模板的 count：

public int findCircleNum(int[][] isConnected) {
    int n = isConnected.length;
    UnionFind uf = new UnionFind(n);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {   // 对称矩阵，只看一半
            if (isConnected[i][j] == 1) uf.union(i, j);
        }
    }
    return uf.getCount();
}

684. 冗余连接

给一棵加了"多余一条边"的树，找出这条多余边。逐条加边：如果这条边的两端已经是同根（加它之前就连通），那它就是成环的多余边，直接返回：

public int[] findRedundantConnection(int[][] edges) {
    UnionFind uf = new UnionFind(edges.length + 1);  // 节点从 1 编号
    for (int[] edge : edges) {
        if (uf.connected(edge[0], edge[1])) {
            return edge;        // 加之前已连通 → 这条边导致环
        }
        uf.union(edge[0], edge[1]);
    }
    return new int[0];
}

这个解法能体现并查集的精髓：不需要真把图画出来，连通关系边到边查。685（有向版的冗余连接）在此基础上多一个入度讨论，思路相通。

200. 岛屿数量：并查集 vs DFS/BFS 对照

同一个经典题给三种解法，感受差异：

维度	DFS 淹岛	BFS	并查集
核心动作	扫网格，遇 1 就递归淹掉	扫网格，遇 1 就入队扩散	相邻两个 1 就 union
防重复	直接改 grid	visited 矩阵	根节点天然分块，count 维护
复杂度	O(mn) 时间，最坏 O(mn) 递归栈	O(mn) 时间，队列 O(min(m,n))	O(mn·α) 时间，O(mn) 数组
特点	代码最短	无栈溢出风险	可支持"边输入边统计"

并查集版核心：给每个格子编号 id = i * col + j，陆地上扫右、扫下两个方向做 union，水格子单独跳过：

public int numIslands(char[][] grid) {
    int rows = grid.length, cols = grid[0].length;
    UnionFind uf = new UnionFind(rows * cols);
    int water = 0;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == '0') { water++; continue; }   // 水先记数
            // 只需向右、向下两个方向连，避免重复
            if (j + 1 < cols && grid[i][j + 1] == '1')
                uf.union(i * cols + j, i * cols + j + 1);
            if (i + 1 < rows && grid[i + 1][j] == '1')
                uf.union(i * cols + j, (i + 1) * cols + j);
        }
    }
    return uf.getCount() - water;           // 总块数减去水格子数
}

六、什么时候选并查集？

选并查集的信号：边是动态加入的、只需回答"是否连通/有几个块"、不需要输出路径或遍历顺序。典型：冗余连接判环、动态加边、Kruskal 最小生成树里判断边两端是否已连通。

选 DFS/BFS 的信号：需要遍历过程本身——求路径、求面积/步数、按层处理、方向性约束（如只能往低处流）。连通关系是静态且一次性给全的话，DFS 通常代码更短。

一句话：只要"连通性"不要"过程"，优先并查集；要"过程"，DFS/BFS。

七、LeetCode 题目清单

题号	题名	一句话考点
547	省份数量	矩阵建图，数连通块个数
684	冗余连接	加边前已连通的边即成环边
685	冗余连接 II	有向树：入度分析 + 并查集
1971	寻找图中是否存在路径	并查集判连通裸题
200	岛屿数量	网格编号后相邻 union
990	等式方程的可满足性	先合并 == 再检查 != 矛盾
128	最长连续序列	值域并查集合并相邻数（哈希表法更常用）

参考

代码随想录 · 并查集