最近在 LeetCode 的每日一题中，大量出现了使用并查集进行算法设计的题目，如「684.冗余连接」、「803.打砖块」、「947.移除最多的同行或同列石头」。并查集这一点本身并不难学习，但有时候在题目中不容易发现对应的连接关系。
什么是并查集？
并查集是一种树形的数据结构，旨在通过特定的规则，将属于同一类别的点归于一个树中，构成一个集合。其包括两种基本操作：
- 合并（Union）：将两个不同的集合合并为一个集合，或者将新的元素合入特定的集合
- 查找（Find）：确定两个元素是否在同一个集合中，或者确定某个元素处于哪一个子集
注意：虽然并查集是一个树形的数据结构，但考虑到内存以及时空复杂度，一般都会使用数组或者列表来实现，而非 Node 树结点。
建树初始化
首先，需要根据当前数据的规模来开辟空间，同时确保原始数据能够 One-Hot 地映射到创建的节点集合中，即创建的空间能够包括所有的原始数据。下面是样板代码（Python）：
class Union:
def __init__(self, N):
self.p = list(range(N)) # 初始化列表，每一个节点的值等于索引，其中 N 要根据原始数据确定
这一部分不难理解，即开辟一块额外的空间来保存并查集中的父子关系，因为现在还没有初始化关系，所以每一个点都指向自己的位置。接下来便是合并（Union），目的是输入数据形成并查集，样板代码如下：
def find(self, x):
if x != self.p[x]:
self.p[x] = self.find(self.p[x]) # 这里的递归是为了压缩路径，加快查找速度，下面会讲到
return self.p[x]
find() 会返回该点所对应集合的根（父亲），如果两个点返回同样的根（父亲），则证明其处于同一个集合中。
一般情况下合并的样本代码如下：
def union(self, x, y):
xr = self.find(x) # 找出 x 对应的根
yr = self.find(y) # 找出 y 对应的根
self.p[xr] = yr # 将 x 的根指向 y 的根，因为其属于同一个集合
不同的题目用到的数据不同，一般是某个点的坐标 (x, y) 之类。这类题往往都可以使用递归、DP 等方法解决，所以我经常会往递归和 DP 的方向去想，然后卡在某个状态上（暴风哭泣），从而忘了直接用更简单的并查集来解。
举个例子
下面举两个例子：
「947.移除最多的同行或同列石头」
class Solution:
def removeStones(self, stones: List[List[int]]) -> int:
uf = Union(20000) # 开辟空间
for x, y in stones:
uf.union(x, y + 10000) # 前半部分存储 x，后半部分存储 y，防止数据冲突
return len(stones) - len({uf.find(x[0]) for x in stones})
解释一下最后的 return 部分：在前面的构建并查集的过程中，我们已经把每个石头的横纵坐标一起构建了一个并查集。相同的行或者相同的列都已经归于一个集合中，所以对这些石头的坐标查找根（父亲）结点，都会返回相同的值。
所以基于这个特点，uf.find(x[0]) for x in stones 返回的是每个石头对应的根的列表。然后套一个 {} 对列表求 set，即共有多少个不同的根，这便代表着有多少个石头不能被删除，所以 len(stones) - len({uf.find(x[0]) for x in stones}) 即为可以删除的石头数量。
因为不管是 x 还是 y，都在一个集合中，所以使用 x[0] （石头的横坐标）或者 x[1] （石头的纵坐标）来计算结果是一致的。
「684.冗余连接」
# 并查集 class 中的 connected 函数如下：
def connected(self, p, q):
return self.find(p) == self.find(q)
# 题解
class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
uf = UF(1001) # 开辟内存空间
for fr, to in edges:
if uf.connected(fr, to): return [fr, to]
uf.union(fr, to)
这题的意思就是根据向量 [x, y] 来构建一张图，然后删除其中环的一条冗余边，使其变成一个无环图。connected() 用来判断两个点是否属于同一个集合中，如果两点属于同一个集合，则这一条向量连接后便会形成环，因此可删除，return 即可；如果不是同一个集合，则将其放入并查集构建树。
路径压缩
路径压缩是为了使查找这一过程更快，一般使用的方法有递归合并和按秩合并。
递归合并
每加入一个结点，就把该点对应的值设为其所属集合的根，这样查找就不需要每次从头递归了，大大减少了时间消耗。比如前面的代码：
def find(self, x):
if x != self.p[x]:
self.p[x] = self.find(self.p[x]) # 这里的递归是为了压缩路径，加快查找速度
return self.p[x]
这样的路径压缩方法对于大多数的算法题已经够用了，但是如果遇到了对时间卡的很紧，还外加一些阴间样例的题目，这样的方法可能依旧会翻车。
其原因就是在于，当一个大的集合要与小的集合合并时，如果使用递归合并，就有可能出现大的往小的集合合并的情况，此时需要就大集合的根依次改为小集合的根，这回额外消耗更多的时间。
按秩合并（启发式合并）
所以针对这种情况，我们就需要另外建立一个变量“秩（Rank）”来存储每一个树的深度信息（因为只有深度会影响到递归的效率），这样我们就能够在合并集合的时候，始终让较浅的集合合并到较深的集合处，从而有效地减少所合并所消耗的时间。
使用启发式合并的代码样例（注意其中的 Rank 列表）：
class Solution:
def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:
# ==================== 并查集模版 =========================
def find(x):
parent.setdefault(x,x)
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
rootx, rooty = find(x), find(y)
if rootx != rooty:
if rank[rootx] < rank[rooty]:
parent[rootx] = rooty
count[rooty] += count[rootx]
else:
parent[rooty] = rootx
count[rootx] += count[rooty]
if rank[rootx] == rank[rooty]: rank[rootx] += 1