并查集是什么？

并查集，也称之为不相交数据集合，是一种用于管理不重叠动态集合的数据结构。这个解释太过官方，有点不太好理解。其实它主要解决的是我们有一个主要集合，里面有很多元素，我们现在要快随判断这些元素一共有多少组，也要快速返回每一个元素属于哪个组的问题。

换个说法

1. 并查集是一种很特殊的数结构
2. 一般我们的树结构是父节点指向子节点，而现在并查集是子节点指向父节点

并查集基本概念

• 父节点数组：用来表示每个元素所属集合的代表元素。初始化的时候，每个元素的父节点都是它自己本身
• 集合代表元素： 每个集合都有一个代表元素，就像是我们开会的时候，每个班级选一个代表去参加，这个代表就代表整个班级的所有同学
• 秩： 两个代表的集合合并的时候，要选举一个新的代表代表合并之后的集合，选举新的代表的时候就要参考两个集合的秩，主要是为了降低数的高度

并查集主要解决什么问题？

简单说，并查集主要解决的是连通性的问题

并查集广泛应用于解决图论问题中的连通性问题，例如检测无向图中的环、计算森林中树木的数量、Kruskal算法构建最小生成树等。

并查集的数据结构非常简单且高效，特别是在经过路径压缩和按秩合并优化后，它的性能表现非常好，几乎可以在常数时间内完成查找和合并操作。

并查集的常见操作

接口定义：

java">public interface UnionFind {void union(int p, int q);int find(int p);
}

union用来进行合并，把两个子集合的元素合并成一个集合。我们还需要一个find方法用来返回它集合的代表节点。

我们首先实现第一个最简单版本的并查集

并查集的实现

版本一

我们初始化了一个数组，每个数组的初始代表节点都是它自己本身。union的时候，我们不考虑每个子集合元素的多少，都是取右边元素为新的子集合的代表节点。

java">public class UnionFind1 implements UnionFind{private int[] id;public UnionFind1(int size) {id = new int[size];for (int i = 0; i < size; i++) {id[i] = i;}}@Overridepublic void union(int p, int q) {int pId = find(p);int qId = find(q);if (pId == qId) {return;}for (int i = 0; i < id.length; i++) {if (id[i] == pId) {id[i] = qId;}}}@Overridepublic int find(int p) {return id[p];}}

find的时间复杂度是O（1）
union的时间复杂度是O（n）

但是这个合并的时候不考虑每个元素的大小，很有可能造成，大集合的代表变成小集合的代表，这意味了每个大集合都要去修改自己的父节点，这样的效率肯定是不高的
打个现实生活中的比方，两个村子合并成一个村子；一个村子10000人，另一个10人。我们现在实现的算法，有可能导致10000人的村子改正10人村子的代表，这肯定是效率不高。

版本二

版本一存在的问题在于union的时候，要改动的元素很多，时间复杂度是O（n）。有没有办法可以减少union的开销呢？因为我们并查集的合并操作是比较频繁的。

java">public class UnionFind2 implements UnionFind{private int[] parent;public UnionFind2(int size) {parent = new int[size];for (int i = 0; i < size; i++) {parent[i] = i;}}@Overridepublic void union(int p, int q) {int pParent = find(p);int qParent = find(q);if (qParent == pParent) {return;}parent[pParent] = qParent;}@Overridepublic int find(int p) {while (p != parent[p]) {p = parent[p];}return p;}
}

版本二的 union的时候，要更改的只有一个元素，p节点的代表节点改成q节点的代表节点。这样union的时候要改动的元素数量下降了；代价是find操作比版本一的性能下降了。但是版本二的union的时候还是没有考虑两个子集合的大小。

版本三

我们版本三要在版本二的基础上，考虑子集合的大小。这个也是有成本的，我们需要新开一个数组记录size。相当于以空间换时间。

java">public class UnionFind3 implements UnionFind{private int[] parent;private int[] sizes;public UnionFind3(int size) {parent = new int[size];sizes = new int[size];for (int i = 0; i < size; i++) {parent[i] = i;sizes[i] = 1;}}@Overridepublic void union(int p, int q) {int pParent = find(p);int qParent = find(q);if (qParent == pParent) {return;}if (sizes[qParent] > sizes[pParent]) {parent[pParent] = qParent;sizes[qParent] += sizes[pParent];}else {parent[qParent] = pParent;sizes[pParent] += sizes[qParent];}}@Overridepublic int find(int p) {while (p != parent[p]) {p = parent[p];}return p;}
}

版本四

版本三我们考虑了合并的时候的每一个子集合的size，还有别的优化点吗？ 其实我们的并查集是一个特殊的树形结构，树形结构的新能尤其是查找的性能跟高度高度相关。我们基于size的版本在一些特殊情况下，性能还有优化的空间。比如一个子集合有100个元素，但是高度是2；另一个是10个元素但是是倾斜二叉树，或者说极端一点退化成一个链表的数结构，这样的话其实我们应该把100个元素的挂在倾斜的10个元素的集合上，这样我们的树结构高度才不会进一步倾斜。

java">public class UnionFind4 implements UnionFind{private int[] parent;private int[] rank;public UnionFind4(int size) {parent = new int[size];rank = new int[size];for (int i = 0; i < size; i++) {parent[i] = i;rank[i] = 1;}}@Overridepublic void union(int p, int q) {int pParent = find(p);int qParent = find(q);if (qParent == pParent) {return;}if (rank[qParent] > rank[pParent]) {parent[pParent] = qParent;}else if(rank[qParent] < rank[pParent]){parent[qParent] = pParent;}else {parent[pParent] = qParent;rank[qParent]++;}}@Overridepublic int find(int p) {while (p != parent[p]) {p = parent[p];}return p;}
}

版本五

我们现在优化的空间还有吗？ 还有的，其实我们理想中的树要想保证效率都是尽可能越扁平越好，所以我们还可以使用的一个优化策略就是路径压缩。

java">public class UnionFind5 implements UnionFind {private int[] parent;private int[] rank;public UnionFind5(int size) {parent = new int[size];rank = new int[size];for (int i = 0; i < size; i++) {parent[i] = i;rank[i] = 1;}}@Overridepublic void union(int p, int q) {int pParent = find(p);int qParent = find(q);if (qParent == pParent) {return;}if (rank[qParent] > rank[pParent]) {parent[pParent] = qParent;}else if(rank[qParent] < rank[pParent]){parent[qParent] = pParent;}else {parent[pParent] = qParent;rank[qParent]++;}}@Overridepublic int find(int p) {if (p != parent[p]) {parent[p] = find(parent[p]);}return p;}
}

观察这段代码，我们主要是在find的时候，直接把p挂在代表节点下面，这样我们每次find的时候都相当与把树尽可能的扁平化。这样的话，我们查找或者union的性能都是很高的。

并查集算法题应用案例

Leetcode 200. 岛屿数量

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。

输入：grid = [
[“1”,“1”,“1”,“1”,“0”],
[“1”,“1”,“0”,“1”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“0”,“0”,“0”]
]
输出：1

输入：grid = [
[“1”,“1”,“0”,“0”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“1”,“0”,“0”],
[“0”,“0”,“0”,“1”,“1”]
]
输出：3

我们使用并查集解决这个问题
其实这个问题不就是相当于给了我们一个大的集合，让我们找到里面有几个子集合。也是一种连通性问题，正好可以通过我们的并查集解决这个问题。当然这个题目还有其他解决方法。

java">class Solution {int[] parent;int[] rank;int res;int find(int i) {while (i != parent[i]) {i = parent[i];}return parent[i];}public void union(int p, int q) {int pRoot = find(p);int qRoot = find(q);if (qRoot == pRoot) {return;}if (rank[qRoot] > rank[pRoot]) {parent[pRoot] = qRoot;} else if (rank[qRoot] < rank[pRoot]) {parent[qRoot] = pRoot;} else {parent[pRoot] = qRoot;rank[qRoot]++;}res--;}public int numIslands(char[][] grid) {int m = grid.length;int n = grid[0].length;parent = new int[m * n];rank = new int[m * n];res = 0;//初始化 parent 数组，记录初始岛屿数（也就是 1 的数目）for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {int idx = i * n + j;parent[idx] = idx;if (grid[i][j] == '1')res++;}}for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {int idx = i * n + j;if (grid[i][j] == '1') {if (i + 1 < m && grid[i + 1][j] == '1') { //合并岛屿union(idx, (i + 1) * n + j);}if (j + 1 < n && grid[i][j + 1] == '1') {union(idx, i * n + j + 1);}}}}return res;}
}

注释已经加上了，如果有疑问，也欢迎大家讨论，也欢迎私信交流。
TODO ： 希望之后能有时间，把各个版本的优化能做成动画贴上来，更加直观一点。