并查集专门解决“分组”和“连通性”问题。两个元素是否属于同一组？合并两个集合后还有几个连通分量？图里加一条边是否会成环？这些都可以用并查集处理。

面试里它的代码不长，但 find 写不好会直接影响复杂度。

find

文章内容概览：

什么是并查集？

并查集如何用数组表示集合？

find、union、connected 分别做什么？

find
union
connected

路径压缩和按大小合并为什么能提速？

并查集适合哪些连通性问题？

并查集用父节点指针表示连通分量的森林结构

什么是并查集？

什么是并查集？

并查集（Disjoint Set Union，DSU，也叫 Union Find）维护的是一组互不相交的集合。它最擅长回答两类问题：

查询：两个元素现在是不是属于同一个集合？

合并：把两个元素所在的集合合并成一个集合。

它不关心集合内部的完整结构，也不关心两个点之间具体经过哪些边。比如在社交关系里，并查集可以快速告诉你 A 和 B 是否属于同一个关系网络；但它不会告诉你 A 到 B 的最短路径是什么。

这也是并查集和 BFS/DFS 的区别：BFS/DFS 更像是每次沿着图现场搜索；并查集则是把连通关系在合并过程中维护起来，后续查询直接看两个元素的代表节点是否一致。

并查集如何表示集合？

并查集如何表示集合？

并查集通常用一个 parent 数组表示若干棵树组成的森林：

parent

parent[x] 表示元素 x 的父节点。

parent[x]
x

如果 parent[x] == x，说明 x 是所在集合的根节点。

parent[x] == x
x

一个集合只需要用根节点作为代表。

初始化时，每个元素都是一个单独的集合，所以每个元素的父节点都是自己：

parent[0] = 0
parent[1] = 1
parent[2] = 2
...
parent[0] = 0
parent[1] = 1
parent[2] = 2
...

执行 union(0, 1) 后，可以让 1 的根节点挂到 0 的根节点下面。此时 0 和 1 就属于同一个集合。继续执行 union(1, 2) 时，虽然传入的是 1 和 2，但真正合并的是 1 的根节点和 2 的根节点。

union(0, 1)
1
0
0
1
union(1, 2)
1
2
1
2

所以，并查集里的关键不是“当前节点的父节点是谁”，而是“沿着父节点一直往上走，最终根节点是谁”。find(x) 做的就是这件事。

find(x)

三个核心操作

三个核心操作

并查集常见操作可以概括为三个：

操作作用find(x)找到 x 所在集合的代表节点，也就是根节点union(a, b)合并 a 和 b 所在的两个集合connected(a, b)判断 a 和 b 的代表节点是否相同

操作作用

操作

作用

find(x)找到 x 所在集合的代表节点，也就是根节点

find(x)

find(x)

找到 x 所在集合的代表节点，也就是根节点

x

union(a, b)合并 a 和 b 所在的两个集合

union(a, b)

union(a, b)

合并 a 和 b 所在的两个集合

a
b

connected(a, b)判断 a 和 b 的代表节点是否相同

connected(a, b)

connected(a, b)

判断 a 和 b 的代表节点是否相同

a
b

如果两个元素的根节点相同，说明它们已经属于同一个集合；如果根节点不同，union 就把其中一个根节点挂到另一个根节点下面。

union

面试考察重点

面试考察重点

能写 find 和 union。

find
union

能解释路径压缩的作用。

能用并查集统计连通分量。

能处理图中判环、朋友圈、省份数量、等式关系。

能说明并查集适合动态合并，不适合频繁删除。

从 Quick Find 到 Quick Union

从 Quick Find 到 Quick Union

理解并查集时，可以先看两个极端版本：

Quick Find：数组里直接存每个元素所属集合编号。查询两个元素是否同组很快，但合并两个集合时，需要扫描整个数组修改集合编号。

Quick Union：数组里存父节点，通过根节点代表集合。合并时只改一个根节点的父指针，但如果树很高，find 会变慢。

find

面试和刷题里常用的是 Quick Union 的优化版本：路径压缩 + 按大小/秩合并。

路径压缩：每次 find(x) 时，把沿途节点直接挂到根节点下面，后续再查这些节点会更快。

find(x)

按大小合并：合并两个集合时，把小树挂到大树下面，尽量避免树长得太高。

这两个优化配合起来，能把并查集的多次操作压到非常接近常数时间。

基础模板

基础模板

class UnionFind {
    private final int[] parent;
    private final int[] size;
    private int count;

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

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

    boolean union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA == rootB) {
            return false;
        }
        if (size[rootA] < size[rootB]) {
            parent[rootA] = rootB;
            size[rootB] += size[rootA];
        } else {
            parent[rootB] = rootA;
            size[rootA] += size[rootB];
        }
        count--;
        return true;
    }

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

    int count() {
        return count;
    }
}
class UnionFind {
    private final int[] parent;
    private final int[] size;
    private int count;

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

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

    boolean union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA == rootB) {
            return false;
        }
        if (size[rootA] < size[rootB]) {
            parent[rootA] = rootB;
            size[rootB] += size[rootA];
        } else {
            parent[rootB] = rootA;
            size[rootA] += size[rootB];
        }
        count--;
        return true;
    }

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

    int count() {
        return count;
    }
}

parent[x] 表示 x 的父节点。根节点的父节点是自己。路径压缩会让查找路径上的节点直接挂到根节点下面，后续查询更快。

parent[x]
x

这份模板里有两个细节值得单独看：

find() 中的 parent[x] = find(parent[x]) 是路径压缩。递归返回根节点后，顺手把 x 直接连到根节点。

find()
parent[x] = find(parent[x])
x

union() 中通过 size 决定谁挂到谁下面，这是按大小合并。这样可以减少树的高度增长。

union()
size

count 表示当前还有多少个连通分量。每次 union() 真正合并了两个原本不连通的集合，count 才减 1；如果两个元素本来就连通，不能重复减少。

count
union()
count

复杂度

复杂度

使用路径压缩和按大小合并后，并查集单次操作的均摊复杂度是 O(α(n))，其中 α(n) 是反阿克曼函数，增长极慢。实际面试里一般说“近似常数时间”即可。

O(α(n))
α(n)

空间复杂度是 O(n)，主要来自 parent 和 size 数组。

O(n)
parent
size

典型场景

典型场景

场景处理方式判断两个节点是否连通比较 find(a) 和 find(b)合并两个集合union(a, b)统计连通分量个数初始化为 n，每次成功合并减 1判断无向图是否有环如果一条边两端已连通，再加边就成环等式方程先合并相等关系，再检查不等关系是否冲突

场景处理方式

场景

处理方式

判断两个节点是否连通比较 find(a) 和 find(b)

判断两个节点是否连通

比较 find(a) 和 find(b)

find(a)
find(b)

合并两个集合union(a, b)

合并两个集合

union(a, b)

union(a, b)

统计连通分量个数初始化为 n，每次成功合并减 1

统计连通分量个数

初始化为 n，每次成功合并减 1

n

判断无向图是否有环如果一条边两端已连通，再加边就成环

判断无向图是否有环

如果一条边两端已连通，再加边就成环

等式方程先合并相等关系，再检查不等关系是否冲突

等式方程

先合并相等关系，再检查不等关系是否冲突

并查集特别适合“关系不断合并、查询是否同组”的问题，例如省份数量、冗余连接、账户合并、最小生成树中的 Kruskal 算法等。

不过，并查集不擅长处理删除关系。因为一旦两个集合合并，内部哪些边让它们连通的信息通常已经被压缩掉了。删除一条边后，集合是否仍然连通并不能靠简单修改 parent 数组得到。

parent

易错点

易错点

find 里要返回根节点，不是返回父节点。

find

路径压缩不要写丢递归返回值。

union 时只有两个集合原本不连通，连通分量数量才减 1。

union

并查集适合合并，不擅长删除关系。

二维网格题需要把 (i, j) 映射成一维编号，例如 i * cols + j。

(i, j)
i * cols + j

推荐练习题

推荐练习题

  1. 省份数量

547. 省份数量

  1. 冗余连接

684. 冗余连接

  1. 等式方程的可满足性

990. 等式方程的可满足性

  1. 连通网络的操作次数

1319. 连通网络的操作次数

  1. 岛屿数量

200. 岛屿数量

参考资料

参考资料

Algorithms, 4th Edition：Union-Find

Algorithms, 4th Edition：Union-Find

Algorithms, 4th Edition：WeightedQuickUnionPathCompressionUF

Algorithms, 4th Edition：WeightedQuickUnionPathCompressionUF

CP-Algorithms：Disjoint Set Union

CP-Algorithms：Disjoint Set Union

写在最后

写在最后

如果内容对你有帮助的话，欢迎顺手给 JavaGuide 点一个免费的 Star 支持一下：GitHub | Gitee。

GitHub

Gitee

JavaGuide 已持续维护近七年，累计 6100+ 次提交，来自 620+ 位贡献者共同完善。你的 Star、反馈和 PR，都是这个项目继续更新的动力。

如果你正在准备后端/AI 应用开发面试，也可以了解一下我的知识星球，里面包括后端和 AI 实战项目、简历优化、一对一提问和高频考点资料，已经持续维护六年。

知识星球