一、什么是并查集
并查集被很多OIer认为是最简洁而优雅的数据结构之一，主要用于处理一些不相交集合的合并问题，并支持两种操作：
- 合并（Union）：把两个不相交的集合合并为一个集合。
- 查询（Find）：查询两个元素是否在同一个集合中。
当然，这样的定义让人感觉摸不着头脑，我们来一个样例进行分析。
二、实现并查集
并查集的初始化：
class UnionAndFind() { // 自己的大哥是谁 private int[] parent; // 自己的队伍有多少人 private int[] size; // 江湖还有几个派系 int sets; // 初始化 // 每个人的大哥都是自己 // 每个队伍的人数都为1 public UnionAndFind(int N) { parent = new int[N]; size = new int[N]; help = new int[N]; sets = N; for (int i = 0; i < N; i++) { parent[i] = i; size[i] = 1; } } }
并查集的 查询（Find） 方法：这里的时间复杂度可以降低到O(1)级别，不敢相信吧，那就往下看吧
// 查询a和b在不在一个阵营中 public boolean isSameSet(int a, int b) { return find(a) == find(b); } // 看一下你的最终大哥是谁 public int find(int i){ while(i != parent[i]){ i = parent[i]; } return i; }
并查集的 合并（Union）方法：先去找到两个参数的最终大哥，小弟少的大哥跟着小弟多的大哥混
public void union(int a, int b) { int A = find(a); int B = find(b); if (A != B) { if (size[A] >= size[B]) { size[A] += size[B]; parent[B] = A; } else { size[B] += size[A]; parent[A] = B; } sets--; } }
三、真题训练
- 初始化数组，拷贝上述并查集即可
public int findCircleNum(int[][] isConnected) { int N = isConnected.length; UnionAndFind unionFind = new UnionAndFind(N); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (isConnected[i][j] == 1 && i != j) { unionFind.union(i, j); } } } return unionFind.sets; }
四、路径压缩优化
我们目前的并查集已经可以解决大部分问题，但是，我们能够对目前的并查集版本进行路径压缩优化。
我们可以发现，在我们 find() 方法时，我们会进行一个 while() 循环的查找大哥的操作，这种操作十分的浪费时间，有没有什么办法可以进行下优化呢？
如下所示：
我们可以看到对于6、5、3之类来说，每次进行 find 查询的时候，都需要经过2~3次的循环才能够找到1。
如果我们在进行查找的时候，保存一下值，然后重新挂到1的上面，比如：
我要查询下6，肯定会查询找5、3，这个时候，我们把6、5、3保存到临时数组中，在查询完毕后，将这些数组直接挂到1的下面，这样的话，下次查询会降低循环的次数。
当我们查询的次数远远大于我们的数据量时，这个时候 find() 的操作就已经变成了一个O(1)级别的查询时间。
public int find(int i) { int h = 0; while (i != parent[i]) { help[h++] = i; i = parent[i]; } for (h--; h >= 0; h--) { parent[help[h]] = i; } return i; }
五、总结
并查集算法通常用在处理一些不交集（Disjoint Sets）的合并及查询问题
力扣也有并查集的 tag 专栏：并查集
大家可以好好体会一下路径压缩的奇妙，通过不断的路径压缩，可以将我们的时间复杂度降低到O(1)
这里可能有小伙伴有疑问，为啥是O(1)，你就算挂在1的下面，不也得查询两次嘛
对于时间复杂度来说，只要是常数的次数都可以认定为O(1)的时间复杂度，况且，你也可以使用HashMap来进行存储
