专题 20并查集（Disjoint Set Union）：动态连通性利器

20.1并查集解决什么：动态连通性

并查集管理的是若干个互不相交的集合，支持两个操作：

• union(a, b)：把 a 所在的集合和 b 所在的集合合并成一个；
• find(a)：返回 a 所在集合的「代表元」（根），用它来判断两点是否同组——find(a) == find(b) 即同组。

一个好懂的类比：把每个人看成节点，一开始人人「单干」（各自是一个集合）。union 就是「结拜」——两人拜把子后属于同一个帮派；帮派用「老大（根）」来标识。问「A 和 B 是不是一伙的」，只要看两人的老大是不是同一个。

初始：1  2  3  4  5   （5 个独立集合，各自是自己的根）
union(1,2)：1 和 2 同帮，老大设为 1
union(3,4)：3 和 4 同帮，老大设为 3
union(2,3)：2 的老大是 1，3 的老大是 3 → 把 1 和 3 合并，老大统一
现在 find(1)==find(4) → true（1-2-3-4 一伙）
find(5) 还是单独 → 与 1 不同伙

和 DFS 连通性的区别：DFS 是「图建好后一次性判断」，并查集支持边加边查——每来一条新边就 union，每来一个提问就 find，全程 Online，均摊 O(1)。

一个直觉：并查集 vs 拉帮结派

把并查集想象成校园里的「社团合并」：

正因为「问话时顺手压缩路径」「合并时小并大」，所以无论社团怎么分合，每次查询都接近 O(1)——这正是并查集快的核心。

20.2模板：find + union

最关键的优化有两个，缺一不可，否则会退化：

• 路径压缩（Path Compression）：find 时顺手把沿途节点的父指针直接指向根，下次再 find 就一步到位；
• 按秩合并（Union by Rank）：合并时把「较矮的树」挂到「较高的树」下面，避免树被拉成链。

两个优化一起上，单次 find/union 的均摊时间复杂度近似 O(1)（严格说是反阿克曼函数 α(n)，增长极慢，可当常数）。

参考代码（通用模板）

class DSU {
    int[] parent;   // parent[i] = i 所在树的根的父（根指向自己）
    int[] rank;     // rank[i] = 以 i 为根的树的高度上界（用于按秩合并）

    public DSU(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;   // 初始：每个人自立门户
            rank[i] = 0;     // 高度从 0 起
        }
    }

    // 找根 + 路径压缩：沿途节点的父都直接指向根
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 递归压缩，把 x 的父改成根
        }
        return parent[x];
    }

    // 合并两集合：按秩合并，矮树挂到高树底下
    public void union(int x, int y) {
        int rx = find(x);
        int ry = find(y);
        if (rx == ry) return;     // 已经同根，无需合并
        if (rank[rx] < rank[ry]) {
            parent[rx] = ry;      // rx 较矮，挂到 ry 下
        } else if (rank[rx] > rank[ry]) {
            parent[ry] = rx;      // ry 较矮，挂到 rx 下
        } else {
            parent[ry] = rx;      // 一样高，任选其一，rx 高度 +1
            rank[rx]++;
        }
    }

    // 判同组
    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }
}

20.3省份数量（中等，力扣 547）

中等 核心：对称矩阵建集合，数根个数

题意：有 n 个城市，给一个 n×n 的矩阵 isConnected，isConnected[i][j] = 1 表示城市 i 和城市 j 直接相连（矩阵对称，i=j 为 1）。 「省份」是连通的城市组成的集合（直接或间接相连都算一省）。返回省份数量。

思路推导：每个连通块 = 一个集合

这题本质是「无向图的连通分量计数」。并查集视角：每个城市是节点，isConnected[i][j]=1 就 union(i, j)。全部边 union 完后，有多少个「根节点」（parent[x]==x 的 x）就有多少个省份。

isConnected = [[1,1,0],[1,1,0],[0,0,1]]
城市 0-1 相连 → union(0,1)
城市 2 独立
集合：{0,1}, {2} → 2 个省份
根节点是 0 和 2（parent[x]==x 的个数 = 2）

参考代码

public int findCircleNum(int[][] isConnected) {
    int n = isConnected.length;
    DSU dsu = new DSU(n);
    // 只扫上三角（矩阵对称，避免重复 union）
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (isConnected[i][j] == 1) {
                dsu.union(i, j);   // 相连就合并
            }
        }
    }
    // 数根：parent[x] == x 的就是一个省份的代表
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (dsu.parent[i] == i) count++;
    }
    return count;
}

复杂度

建图遍历矩阵 O(n²)，每次 union/find 近似 O(1)；总 O(n²)。空间 O(n)（DSU 数组）。边界：n=1 返回 1；全 0 矩阵（除对角）返回 n 个独立省份。

20.4冗余连接（中等，力扣 684）

中等 核心：逐条加边，第一次成环的边即答案

题意：给你一棵树（本应 n 个节点 n-1 条边，连通无环），但被多加了一条边变成 n 个节点 n 条边，于是出现一个环。 给你这 n 条边（顺序给出），找出那条导致成环的冗余边返回（若有多种答案，返回在输入里最后出现的那条）。

思路推导：边加边，第一次「已经连通」的就是环

树的性质：n 个节点、连通、无环，则恰有 n-1 条边。现在多一条，多出的那条必然让某两个已经连通的点又连了一次——也就是形成了环。 于是做法很直接：按输入顺序逐条 union 两端点。对当前边 (u, v)，如果 find(u) == find(v) 说明 u 和 v 在加这条边之前就已经同组（已经连通），那这条边就是「多余的那条」，记下它。继续处理后续边，保留最后一条触发连通的边即可。

边按顺序： [[1,2],[2,3],[3,4],[1,4],[1,5]]
union(1,2): 1-2
union(2,3): 1-2-3
union(3,4): 1-2-3-4
union(1,4): find(1)==find(4) 已连通！→ 这条 [1,4] 是冗余
union(1,5): 接上 5（它不构成环，不记）
答案 [1,4]

参考代码

public int[] findRedundantConnection(int[][] edges) {
    int n = edges.length;        // 节点编号 1..n
    DSU dsu = new DSU(n + 1);    // 下标从 1 开始，多开一位
    for (int[] e : edges) {
        int u = e[0], v = e[1];
        if (dsu.connected(u, v)) {
            return e;   // 已连通却还来一条边 → 冗余，直接返回
        }
        dsu.union(u, v);   // 否则正常合并
    }
    return new int[]{};
}

复杂度

遍历边 O(n)，每次 find/union 近似 O(1)，总 O(n)。空间 O(n)。边界：题目保证有解，所以循环内必 return；节点从 1 编号，DSU 开 n+1 避免下标错位。

20.5等式方程的可满足性（中等，力扣 990）

中等 核心：先合并所有 ==，再检查 !=

题意：给一组字符串方程，形如 "a==b" 或 "a!=b"，每个方程用一个小写字母变量。问这些方程能否同时成立（存在一种变量赋值让所有方程都满足）。

思路推导：两遍扫描，顺序不能反

== 表示「必须相等」，把相等的变量合并成一个集合（并查集 union）。 != 表示「必须不等」，即不能在同一集合。关键洞察：先做所有 == 合并，把「被迫相等」的关系全部落实；再扫描 !=，如果某条 != 的两端已经被合并到同一集合（说明它们被迫相等），矛盾，返回 false。

为什么顺序不能反？因为 == 是「合并约束」，必须全部收集完才能知道谁和谁最终同组；如果边扫 == 边查 !=，可能漏掉后续 == 把本应相等的再合并。所以：第一遍只 union 所有 ==，第二遍才 check 所有 !=。

方程： ["a==b","b==c","a==c","b!=c"]
第一遍 union：a-b, b-c, a-c → a,b,c 同组（根为 a）
第二遍 check：b!=c → find(b)==find(c) 同组！矛盾 → false

参考代码

public boolean equationsPossible(String[] equations) {
    DSU dsu = new DSU(26);   // 变量只有 a~z，26 个
    // 第一遍：只合并所有 ==
    for (String eq : equations) {
        if (eq.charAt(1) == '=') {        // "a==b"
            int x = eq.charAt(0) - 'a';
            int y = eq.charAt(3) - 'a';
            dsu.union(x, y);
        }
    }
    // 第二遍：检查所有 !=
    for (String eq : equations) {
        if (eq.charAt(1) == '!') {        // "a!=b"
            int x = eq.charAt(0) - 'a';
            int y = eq.charAt(3) - 'a';
            if (dsu.connected(x, y)) {    // 本应不等却同组 → 矛盾
                return false;
            }
        }
    }
    return true;
}

复杂度

两遍扫描各 O(m)（m 是方程数），每次 find/union 近似 O(1)，总 O(m)。空间 O(26)=O(1)。边界：只有 == 或只有 != 都正常；单变量自比较如 "a==a" 自然通过。

20.6岛屿数量的并查集视角

专题 12 里我们用 DFS 解了「岛屿数量」：对每个陆地格子 DFS 把整块连通陆地淹掉，统计 DFS 启动次数。 那并查集能不能做？能，但要想清楚什么时候该用哪个。

两种解法对比

选型思维：如果题目是「给一张固定的图，问连通块数」，DFS 更顺手——它直接原地标记，不用维护 parent 数组。但如果题目变成「每次新增一块陆地，实时返回当前岛屿数」（力扣 305 岛屿数量 II），DFS 每次重算就太慢，必须用并查集：每加一块新陆地，把它和上下左右已有的陆地 union，并查集 O(1) 维护。

一句话选型：
  图是死的、只问一次   → DFS / BFS（专题 12）
  边加边查、动态连通   → 并查集（本章）

动态版岛屿数量（力扣 305）的并查集写法骨架

为了让你更直观感受「动态」为何必须用并查集，这里给「每次加一块陆地实时返回岛屿数」的骨架：

// 关键思路：维护并查集 + 当前岛屿数 count
// 每加一块陆地 (r,c)：
//   先把它当新岛屿，count++
//   看上下左右四个邻居，若已是陆地且不在同一集合 → union，并 count--
//   （union 成功说明两个岛屿合体，岛屿数减一）
// 返回 count 即可。
// 这样每次加地都是 O(1) 级操作，而 DFS 版本每次要重扫全图 O(mn)。

对比之下，静态题（专题 12 的原版岛屿数量）用 DFS 逐个淹掉连通块，代码更短、不需维护 parent 数组，是更省心的选择。所以工具没有绝对优劣，看问题是否「动态」。

20.7本专题常见坑

20.8自测题