一、并查集：从理解到实战

并查集这东西，说白了就是解决「连通性」问题的利器。我刚开始学的时候觉得它挺玄乎，后来在项目中处理社交关系链时才发现——嗯，真香。

你想想看，生活中很多问题都可以抽象成「两个元素是否属于同一个集合」。比如判断两个城市是否连通、两个用户是否在同一个群组、两个变量是否满足某种等价关系。并查集就是专门干这个的。

1.1 并查集的核心思想

并查集维护的是一堆「集合」。每个集合里选一个代表元素，就像每个班级有个班长。你要判断两个人是不是同班，就看他们的班长是不是同一个人。

它主要干两件事：

• 查找（Find）：找到某个元素所在集合的「代表」
• 合并（Union）：把两个集合合并成一个

我习惯用数组来实现。数组下标表示元素，数组值表示它的父节点。根节点的父节点指向自己。

// 最基本的并查集实现
class UnionFind {
    int[] parent;
    
    public UnionFind(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;  // 每个人都是自己的班长
        }
    }
    
    public int find(int x) {
        while (parent[x] != x) {
            x = parent[x];
        }
        return x;
    }
    
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootY] = rootX;  // 让Y的班长听X的班长指挥
        }
    }
}

这段代码能跑，但效率不高。为什么呢？因为如果一直把长的链往短的链上接，查找时就会越走越深。我曾经在项目中用这个版本处理百万级数据，结果超时了……

1.2 路径压缩：让树变矮

查找的时候，我们其实可以顺手把沿途的节点直接挂到根节点下面。这样下次再查就一步到位了。

public int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);  // 递归压缩
    }
    return parent[x];
}

你看，就加了一行递归。但效果惊人。经过路径压缩后，查找的时间复杂度几乎变成了常数级别。我个人习惯用递归写法，简洁明了。当然你也可以用迭代，看个人喜好。

1.3 按秩合并：让树更平衡

路径压缩解决了「查找慢」的问题，但合并时如果总是把大树往小树上接，还是会形成长链。按秩合并就是来解决这个的。

「秩」可以理解为树的高度。我们总是把矮的树接到高的树上。

class UnionFind {
    int[] parent;
    int[] rank;  // 记录树的高度
    
    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 1;  // 初始高度为1
        }
    }
    
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) return;
        
        // 按秩合并：矮树接高树
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;  // 高度相等时，合并后高度+1
        }
    }
}

1.4 知识体系总览

下面这张图帮你理清并查集的核心脉络：

1.5 经典例题：省份数量

这道题是并查集的入门题。给你一个 n×n 的矩阵 isConnected，isConnected[i][j] = 1 表示城市 i 和城市 j 直接相连。问有多少个省份（连通分量）。

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);
            }
        }
    }
    
    // 统计根节点数量
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (uf.find(i) == i) count++;
    }
    return count;
}

1.6 经典例题：等式方程的可满足性

这道题稍微绕一点。给你一堆等式（a==b）和不等式（a!=b），判断是否所有条件能同时成立。

比如 a==b, b==c, a!=c 就不成立，因为 a 和 c 既相等又不相等。

public boolean equationsPossible(String[] equations) {
    UnionFind uf = new UnionFind(26);  // 26个小写字母
    
    // 第一遍：处理所有等式
    for (String eq : equations) {
        if (eq.charAt(1) == '=') {
            int x = eq.charAt(0) - 'a';
            int y = eq.charAt(3) - 'a';
            uf.union(x, y);
        }
    }
    
    // 第二遍：检查所有不等式
    for (String eq : equations) {
        if (eq.charAt(1) == '!') {
            int x = eq.charAt(0) - 'a';
            int y = eq.charAt(3) - 'a';
            if (uf.find(x) == uf.find(y)) {
                return false;  // 矛盾了
            }
        }
    }
    return true;
}

1.7 总结一下

并查集其实就三个核心操作：初始化、查找、合并。加上路径压缩和按秩合并两个优化，就能应对绝大多数场景。

我个人觉得，并查集是那种「学会一次，受用终身」的数据结构。它简单、高效、实用。你在刷题时遇到「连通性」「等价关系」「分组」这类关键词，可以优先考虑并查集。

好了，这一章就到这里。代码多敲几遍，自然就熟了。

---

公众号:蓝海资料掘金营，微信deep3321