并查集：谁和谁是一伙的

谁和谁是一伙的

亲戚判定：给出若干对「甲和乙是亲戚」，再给出若干组询问「丙和丁是不是亲戚」。亲戚关系会传递——甲和乙是亲戚、乙和丙是亲戚，那么甲和丙也是亲戚。

把每个人看成一个点，每对亲戚关系看成一条边，问题就变成：丙和丁在不在同一个连通块里。第 20 课会讲怎么用遍历回答这个问题，但这里有一条更省的路。

遍历的做法要先把整张图走一遍才能回答一次询问；而这类问题的边会在过程中不断加进来，每来一条边就得重新走一遍。并查集（disjoint set union，缩写 DSU）换了一个想法：别去记录谁和谁直接相连，只记录每个人属于哪个集合。

每个集合挑一个代表

并查集里每个集合挑一个代表元（也叫根）。判断两个人是不是亲戚，只看他们所在集合的代表元是不是同一个——不需要知道中间隔了多少层关系。

存储只需要一个数组：parent[i] 表示「i 的上级是谁」。代表元的上级是它自己。一开始每个人各自成一个集合：

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))     # 一开始每个元素自己就是代表元
        self.size = [1] * n              # 每个集合的大小，按大小合并要用

    def find(self, x):
        while self.parent[x] != x:       # 顺着上级一路往上找
            x = self.parent[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:                     # 已经是一伙的，什么都不用做
            return False
        self.parent[ra] = rb             # 让一个代表元认另一个当上级
        return True

parent 数组画出的是一片森林：每个集合是一棵树，根就是代表元。前面几课学的树在这里又出现了——只不过这次不关心左右孩子，只关心「往上的路通向谁」。

union 里那句 if ra == rb: return False 不是可有可无的。少了它，parent[ra] = rb 会在两个代表元之间来回指，find 就再也走不到头了。

亲戚判定与连通块

两个基本操作搭好之后，两类问题都是一行：

d = DSU(7)
for a, b in [(0, 1), (1, 2), (3, 4), (5, 6)]:
    d.union(a, b)

print('0 和 2 是亲戚:', d.find(0) == d.find(2))
print('0 和 3 是亲戚:', d.find(0) == d.find(3))
print('2 和 3 是亲戚:', d.find(2) == d.find(3))
print('连通块个数:', sum(1 for i in range(7) if d.parent[i] == i))

0 和 2 是亲戚: True
0 和 3 是亲戚: False
2 和 3 是亲戚: False
连通块个数: 3

连通块的个数就是代表元的个数——只有代表元的 parent 指向自己，其余人的 parent 都指着别人。

这两个量对着一道题就够了：判断两点是否连通（第 21 课会拿它和 BFS 对照），以及数连通块。第 21 课的搜索也是这样数连通块的，两者结果必然一致。

合并方向会决定树高

上面那个 union 有一处偷懒：self.parent[ra] = rb 永远是把第一个代表元挂到第二个下面。方向固定，数据一「配合」，树就退化成一条链。

用递增的边 (0, 1), (1, 2), (2, 3), … 试一下，量两件事：树有多高、find 要走多少步。

def height_of(parent):
    h = 0
    for i in range(len(parent)):
        k = 0
        x = i
        while parent[x] != x:
            x = parent[x]
            k += 1
        if k > h:
            h = k
    return h

N = 4000
d = DSU(N)
for i in range(N - 1):
    d.union(i, i + 1)

print('树高', height_of(d.parent))
print('find(0) 走', end=' ')
steps = 0
x = 0
while d.parent[x] != x:
    x = d.parent[x]
    steps += 1
print(steps, '步')

树高 3999
find(0) 走 3999 步

四个元素以上的链，查询就退化成了线性扫描。这正是这一课要防的那件事：并查集的快不是白来的，它取决于树的形状。

路径压缩

第一处改进叫路径压缩（path compression）：find 顺着路往上走的时候，顺手把路上遇到的每个结点都直接挂到根上。

class DSU2(DSU):
    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:          # 把这条路上的人都挂到根上
            self.parent[x], x = root, self.parent[x]
        return root

第一遍走上去找根，第二遍把沿途所有人的上级直接改成根。效果在同一个链上量：

第一次仍然要走满 3999 步（路本来就那么长），但它顺手把路压平了，第二次只要 1 步。这就是「压缩」这个名字的来处。

注意一件事：压缩是在查询时发生的，不是在建树时。同一棵树，压缩之后 height_of 量出来是 1，但它本来有 3999 层高——树高在变，而且是被查询改的。

按大小合并

第二处改进在 union 里：每次把较小的那棵树挂到较大的那棵下面，而不是按固定方向挂。

class DSU3(DSU2):
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.size[ra] < self.size[rb]:      # 让 ra 一定是较大的那个根
            ra, rb = rb, ra
        self.parent[rb] = ra                   # 小的挂到大的下面
        self.size[ra] += self.size[rb]
        return True

为什么这一句就够了？把一个有 s 个结点的树挂到另一棵下面，那 s 个结点的深度各加一。被挂的是较小的那棵，所以一条路每往上走一层，它所在的集合大小至少翻一倍——翻倍最多翻 \log_2 n 次，所以树高不超过 \log_2 n。

这就是第 3 课「规模翻倍才涨一层」那种思路的又一次出现。同样的递增边输入，这一次树高是 1。

两个优化各管什么

两个优化都试一遍，做成一张 2×2 的表。先看形状（链状递增边，n = 4000）：

再看代价。链状输入上做 20 万次查询（n = 20000）：

最后换成 20 万条随机边：

（本机实测。表里的秒数每次运行会浮动，看的是数量级。）

两处值得停一下：

第一，两个优化各自都能独立解决问题。 只上路径压缩，20 万次查询从 101 秒降到 0.036 秒；只按大小合并，降到 0.030 秒。没有「必须两个一起上」这回事——单独任一个都把链状退化消掉了。

第二，两个一起上并不总是更快。 链状那一组里「只按大小」0.0302 秒还比「两个都上」0.0322 秒略快一点；随机边那一组反过来，「两个都上」最快且树高最低（4 层）。原因是路径压缩本身也要花时间改指针，当按大小合并已经把树压到 7 层时，省下的那几步还不够抵掉改指针的开销。

那实践中该怎么办？两个都写上去。 代价是常数级的，而且它把「输入数据恰好对我不利」这件事一起解决了——随机边那组里树高从 7 层降到 4 层就是证据。

它不支持删除

并查集只能合并，不能把已经连起来的拆开。这一条值得单独说，因为需求里「断开」的字样很常见，而并查集接不住。

手搭一棵 p = [0, 0, 1]：0 是根，1 指向 0，2 指向 1，集合是 \{0, 1, 2\}。现在想把 1 摘出去：

p = [0, 0, 1]

def fa(p, x):
    while p[x] != x:
        x = p[x]
    return x

q = list(p)
q[1] = 1                      # 让 1 变成自己的根，看起来是「摘出去」了
print('改动后 p =', q)
print('find(0) =', fa(q, 0), ' find(1) =', fa(q, 1), ' find(2) =', fa(q, 2))

改动后 p = [0, 1, 1]
find(0) = 0  find(1) = 1  find(2) = 1

1 确实单独出来了，但 2 跟着 1 一起被切走了——而 2 原本是穿过 1 才连到 0 的，它和 0 的亲戚关系不该受这次删除影响。

麻烦在于并查集只记录了「上级是谁」，没有记录「谁指着自己」。删掉一个中间结点时，没法知道有多少人靠它连着，也就没法把它们重新接到根上。要支持删除得换一套结构（可持久化并查集、或者干脆别用并查集）。

这一课用到的判断

• 并查集只记录「谁属于哪个集合」，用代表元（根）来区分；判断连通就是比两个根是否相同。
• parent[i] 表示 i 的上级，代表元的上级是自己；这片结构是一片森林，根就是代表元。
• union 里必须先判两个根是否相同，否则 parent[ra] = rb 会造出环，find 再也走不到头。
• 合并方向固定会让树退化成链：递增的边输入下，n = 4000 的树高就是 3999，find 要走 3999 步。
• 路径压缩在查询时压：第一次仍走满全长，第二次就只要 1 步。它改的是树形，所以树高会被查询改变。
• 按大小合并把树高压在 \log_2 n：被挂的是较小的树，一条路每往上一层，集合大小至少翻倍。
• 两个优化各自都能独立解决问题，两个都写上去的代价是常数级的，还能顺带处理不利输入。
• 并查集不支持删除：只记上级、不记下级，删掉中间结点会把挂在它下面的部分一起切走。
• 连通块个数 = 代表元个数，与第 21 课用搜索数出来的结果必然一致。

• OI Wiki · 并查集初始化、查询、路径压缩、启发式合并、复杂度与带权并查集（本课口径出自这里）
• 《算法导论（第 3 版）》第 21 章 用于不相交集合的数据结构书 · 按秩合并与路径压缩的均摊复杂度分析
• 第 17 课：树：会递归的结构parent 数组画的是一片森林，这一课只关心「往上的路通向谁」