并查集
概念理解
在近乎O(1)的时间内，实现：
- 将两个集合合并
- 查找两个元素是否属于一个集合
思想：用树的形式来维护每一个集合
借鉴了树的结构，实现快速合并（Union）以及查找 （Find）操作的数据结构
以整数无序数对为例，考虑以下例子: (1, 2), (2, 3), (6, 7), (5, 6), (7, 4)。把每个数对看做存在着关系，并且假定这种关系具有传递性（很多实际问题正是如此）。现在我们把这些关系聚类。 每个类选出一个代表， 来表示这个类的所有元素（一般是第一个存在于这个类中的元素）
表示方法：用数组来表示：数组下标表示当前元素，该下标对应值为当前元素的代表，如下：
在树表示的集合这：0，4，5 均属于集合3（3是个代表）
在数组表示的集合中，0属于5，5属于3，3属于3，所以0属于集合3
并查集有两个操作，并 和 查，即Union(x, y) 和Find(x).
- Union： 设我们现在要合并
(x, y)， 那么我们要先找出x, y各自的代表（记为father[x],father[y]）。 令一个的代表， 作为另一个的代表即可。 即father[father[a]] = father[b]
- Find： 要查找某个元素的类别， 只需要递归查看其代表元素，直到下标和值相同。即
if x == father[x]: return father[x] else: Find(father[x])
程序框架
class UnionFind: def __init__(self, n): self.root = [] for i in range(n): self.root[i] = i def find(self, x): if x == self.root[x]: return self.root[x] else: return self.find(self.root[x]) def union(x, y): rootX = self.find(x) rootY = self.find(y) if rootX != rootY: self.root[ rootX ] = rootY ''' 整个数据结构非常简洁，解释如下: 1. root数组就是记录每个点的父节点的下标的数组。 对于根节点， num[i] == i root数组 val 位 父节点， 下标为当前值 2. 初始化每个点都是一个独立的树， 自己即为根。 3. 每次查找沿着父节点向上， 直到根节点。 4. 每次合并把一个根节点的父节点设置为另一个根节点。 '''
图解
假设如下集合,
[0, 1, 2] 属于一个集合， 且1为代表；[3, 4, 5]为一个集合，且以3为代表。代表又称为根节点。
find(0) 即查找 0 的代表的过程 ：
union(2, 5)即将2和5集合到同一个代表（根节点）的过程：
并查集的优化
三种优化方法：
- 针对find的：在find的时候，其实是要遍历该分支的，所以可以在遍历的时候顺便进行压缩
- 针对union的：
- union by size：每次将数量较少的集合合并到数量较多的上面
- union by rank：每次将高度较小的合并到高度较高的树上面。
注意：一般针对find的路径压缩是肯定需要的，至于union by size，或者 union by rank 视情况而定，但是优先选择union by size， 因为这样可以知道每个集合的数量，有些题目会要求找出最大的集合，比如最大岛屿的面积，面积即为集合种元素的数量
union by size 的时候，每次都要更新 size, 但是union by rank的时候，只有union的两颗树高度相同时才需要更新高度。
路径压缩的时候是不需要更新 rank的，因为：
可能存在其他更长的路径指向当前root。
此外，rank提供的只是一个下界，而不是真实的实际的高度，下界的存在只是为了避免极端的坏情况。
优化1 Path compression
在 find 的时候，顺便将树状的深度进行压缩。
注意：在路径压缩后，不可以更新 rank， 因为可能存在其他更长的路径指向当前root。此外，rank提供的只是一个下界，若不是真实的实际的高度，下界的存在只是为了避免极端的坏情况
class UnionFind: def __init__(self, n): self.root = [] # 做初始化 for i in range(n): self.root[i] = i def find(self, x): # Path compression if x != self.root[x]: self.root[x] = self.find(self.root[x]) return self.root[x] def union(x, y): rootX = self.find(x) rootY = self.find(y) if rootX != rootY: self.root[rootX] = rootY
优化 2 union by size
再通过一个数组来记录每个集合的元素数量，在union的时候，判断哪个集合的元素数量少，然后将数量多的作为父节点。
该优化方法还有一个附加的作用，那就是可以知道每个集合中的元素数量，在求最大岛屿面积的时候有用。
class UnionFind: def __init__(self, n): self.root = [i for i in range(n)] self.size = [0 for _ in range(n)] def find(self, x): if self.root[x] != x: self.root[x] = self.find(self.root[x]) return self.root[x] def union(self, x, y): root_x = self.find(x) root_y = self.find(y) if root_x != root_y: if self.size[root_x] < self.size[root_y]: self.root[root_x] = root_y self.size[root_y] += self.size[root_x] else: self.root[root_y] = root_x self.size[root_x] += self.size[root_y]
优化 3 union by rank 按秩合并
上述优化方法有个极端情况：节点数多不代表树的高度高，比如按照size的优化方案，执行 Union(2, 5)，元素 2 所在的树总节点数有4个，但只有2层；元素 5 所在的树有3个节点，有3层。见下图：
这个时候可以使用rank来优化，rank代表数的高度或深度。高度低的树向高度高的树合并。
此时，只有 rank 相同的树进行union的时候才更新rank。
class UnionFind: def __init__(self, n): self.root = [i for i in range(n)] self.rank = [1 for _ in range(n)] def find(self, x): if self.root[x] != x: self.root[x] = self.find(self.root[x]) return self.root[x] def union(self, x, y): root_x = self.find(x) root_y = self.find(y) if root_y != root_x: # 不需要更新高度，因为父亲的高度并没有变化,还是最高的 # 比如，此时x接到y下面了，x所在树的高度即y所在树的高度，并没有变化 if self.rank[root_x] < self.rank[root_y]: self.root[root_x] = root_y elif self.rank[root_x] > self.rank[root_y]: self.root[root_y] = root_x # 只有 两边高度相同的时候，才需要更新 当前父亲的高度 else: self.root[root_y] = root_x self.rank[root_x] += 1
经典题目
@1627
速通
并查集 用于处理集合的合并和查询。其时间复杂度，在加上rank和路径压缩优化后为 log* n， 叫做 Iterated logarithm ，近似O(1) 的 。O(log* n) 是比O(log n) 还要快，近似等于O(1)，比O(1)慢一点。