(本来想写个并查集的文章，发现这一篇写得很好，就直接摘抄过来了，也做个记录【union-find】。
1. 概述
并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。有一个联合-查找算法（Union-find Algorithm）定义了两个用于此数据结构的操作：
find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
union：将两个子集合并成同一个集合。
初始化每一个点都是一个连通域，类似下图：
由于支持这两种操作，一个不相交集也常被称为联合-查找数据结构（Union-find Data Structure）或合并-查找集合（Merge-find Set）。为了更加精确的定义这些方法，需要定义如何表示集合。一种常用的策略是为每个集合选定一个固定的元素，称为代表，以表示整个集合。接着，find(x) 返回 x 所属集合的代表，而 union 使用两个集合的代表作为参数。
2. 核心API
2.1 find
def find(self, x):
# 未进行路径压缩
while x != self.parent[x]:
x = self.parent[x]
return x
比如下面这个图，调用 find(0) 会逐步找到 3 。
若采用路径压缩方法，在找到 3 的过程上会将路径上的节点都指向根节点。
def find(self, x):
"""
查找节点的父(根)节点
"""
if x != self.parent[x]:
# 进行了路径压缩
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
极限情况下，每一个路径都会被压缩，这种情况下继续查找的时间复杂度就是 。
2.2 union
将其中一个节点挂到另外一个节点的祖先上，这样两者祖先就一样了。也就是说，两个节点联通了。
对于如下的一个图：
图中 r:1 表示 秩为 1，r 是 rank 的简写。记录以该结点为根结点的树的深度。
def union(self, x, y):
"""
合并两个节点，小的树挂到大的树上，使树尽量平衡
"""
p, q = self.find(x), self.find(y)
if p == q:
return
if self.rank[p] < self.rank[q]:
self.parent[p] = q
else:
self.parent[q] = p
if self.rank[p] == self.rank[q]:
self.rank[p] += 1
self.count -= 1
如果我们将 0 和 7 进行一次合并。即 union(0, 7) ，则会发生如下过程。
3. 不带权并查集
完整代码如下：
class UnionFind:
def __init__(self, n):
"""
并查集
:param n: 节点个数
"""
# 记录父节点
self.parent = {}
# 记录以该结点为根结点的树的深度
self.rank = {}
# 记录连通分量的个数
self.count = 0
# 初始化
for i in range(n):
self.parent[i] = I
self.rank[i] = 1
self.count += 1
def find(self, x):
"""
查找节点的父(根)节点
"""
if x != self.parent[x]:
# 进行了路径压缩
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
"""
合并两个节点，小的树挂到大的树上，使树尽量平衡
"""
p, q = self.find(x), self.find(y)
if p == q:
return
if self.rank[p] < self.rank[q]:
self.parent[p] = q
else:
self.parent[q] = p
if self.rank[p] == self.rank[q]:
self.rank[p] += 1
self.count -= 1
4. 带权并查集
实际上并查集就是图结构，我们使用了哈希表来模拟这种图的关系。 而上面讲到的其实都是有向无权图，因此仅仅使用 parent 表示节点关系就可以了。而如果使用的是有向带权图呢？实际上除了维护 parent 这样的节点指向关系，我们还需要维护节点的权重，一个简单的想法是使用另外一个哈希表 weight 存储节点的权重关系。比如 weight[a] = 1 表示 a 到其父节点的权重是 1。
如果是带权的并查集，其查询过程的路径压缩以及合并过程会略有不同，因为我们不仅关心节点指向的变更，也关心权重如何更新。比如：
a b
^ ^
| |
| |
x y
如上表示的是 x 的父节点是 a，y 的父节点是 b，现在我需要将 x 和 y 进行合并。
a b
^ ^
| |
| |
x -> y
假设 x 到 a 的权重是 w(xa)，y 到 b 的权重为 w(yb)，x 到 y 的权重是 w(xy)。合并之后会变成如图的样子：
a -> b
^ ^
| |
| |
x y
那么 a 到 b 的权重应该被更新为什么呢？我们知道 w(xa) + w(ab) = w(xy) + w(yb)，也就是说 a 到 b 的权重 w(ab) = w(xy) + w(yb) - w(xa)。
当然上面关系式是加法，减法，取模还是乘法，除法等完全由题目决定，我这里只是举了一个例子。不管怎么样，这种运算一定需要满足可传导性。
完整代码如下：
class WeightedUnionFind:
def __init__(self, n):
"""
:param n: 节点个数
"""
# 记录父节点
self.parent = {}
# 记录到父节点的权重
self.weight = {}
for i in range(n):
self.parent[i] = I
self.weight[i] = 0
def find(self, x):
if x != self.parent[x]:
p, w = self.find(self.parent[x])
self.parent[x] = p
self.weight[x] += w
return self.parent[x], self.weight[x]
def union(self, x, y, w):
p_x, w_x = self.find(x)
p_y, w_y = self.find(y)
if p_x == p_y:
return
self.parent[p_x] = p_y
self.weight[p_x] = w + w_y - w_x
