<aside> <img src="/icons/die1_gray.svg" alt="/icons/die1_gray.svg" width="40px" /> 并查集的数据结构
并查集是一种树型的数据结构，用于处理一些不相交集合的合并与查询问题。
<aside> <img src="/icons/die2_gray.svg" alt="/icons/die2_gray.svg" width="40px" /> 并查集的实现
一个集合构建一棵树，任选一个元素作为该集合的根节点；
记录每个元素的父节点，根节点的父节点为自己本身。
也可以用线性数组实现，数组记录节点的父节点的索引，根节点的父节点索引用-1表示。
</aside>
<aside> <img src="/icons/die3_gray.svg" alt="/icons/die3_gray.svg" width="40px" /> 合并
给定元素关系，将一个集合的树变为另一个集合的子（将一个集合的根节点的父节点改为另一个集合的根节点），如：B的根节点等于A的根节点，这就可以将A和B两棵树合并为一棵树。
</aside>
<aside> <img src="/icons/die4_gray.svg" alt="/icons/die4_gray.svg" width="40px" /> 查询
判断两个元素是否在同一个集合中：从该元素开始访问父节点（一般用递归查找），直到一步步访问到根节点，再对两个元素的根节点进行对比判断（若两个元素的根节点相同则属于同一集合，否则不属于同一集合）。
</aside>
并查集的基本操作
class UnionFind(object):
"""并查集类"""
def __init__(self, n):
"""长度为n的并查集"""
self.father = [-1 for _ in range(n)] # 父节点为-1表示该点为根节点
self.counts = n # 记录并查集里有几个集合
def find(self, p):
"""查找p的根结点(祖先)"""
while self.father[p] > 0:
p = self.father[p]
return p
def union(self, p, q):
"""连通p,q 让q指向p"""
p_root = self.find(p)
q_root = self.find(q)
if p_root != q_root:
self.father[q_root] = p_root # 将q的根节点的父节点设为p的根节点
self.counts -= 1 # 合并1次，集合个数少1
def is_connected(self, p, q):
"""判断pq是否已经连通"""
return self.find(p) == self.find(q) # 即判断两个结点是否是属于同一个祖先
注：并查集的"并”与"查”时间复杂度取决于树的深度。
并查集的路径优化（压缩）
合并的优化：将小树合并到大树，是的每次合并的时候尽量让树的深度不增加。
为了记录树的元素个数，将根节点的父节点用元素个数的负数来代替-1.
查询的优化：在查询的时候直接将当前点的父节点设为它的根节点，以达到树的深度压缩的目的。
查询过B、E、L的根节点后，直接将B、E、L挂到其根节点A下。
class UnionFind(object):
"""并查集类"""
def __init__(self, n):
"""长度为n的并查集"""
self.father = [-1 for _ in range(n)] # 父节点为-1表示该点为根节点
self.counts = n # 记录并查集里有几个集合
def find(self, p):
"""查找p的根结点(祖先)"""
root = p
# 先找到p的根节点
while self.father[root] >= 0:
root = self.father[root]
# 再进行路径压缩
while p != root:
tmp = self.father[p] # 记录p原来的父节点
self.father[p] = root # 将p的父节点设为根节点
p = tmp
return root
def union(self, p, q):
"""连通p,q 让q指向p"""
p_root = self.find(p)
q_root = self.find(q)
if p_root != q_root:
if self.father[p_root] > self.father[q_root]:
# 若p所在树的元素个数较少, 则将p汇入q
self.father[q_root] += self.father[p_root] # 规模相加
self.father[p_root] = q_root
else:
# 否则，将q汇入p
self.father[p_root] += self.father[q_root] # 规模相加
self.father[q_root] = p_root
self.counts -= 1 # 合并1次，集合个数少1
def is_connected(self, p, q):
"""判断pq是否已经连通"""
return self.find(p) == self.find(q) # 即判断两个结点是否是属于同一个祖先
经过优化后，Find操作的最坏时间复杂度为$O(\alpha(n))$，$\alpha(n)$是一个增长很缓慢的函数，通常$\alpha(n)\leq 4$.