并查集

2023-08-06

每个集合用一棵树,根是集合的代表。find 沿父指针往上爬到根,union 把一个根挂到另一个根下。加上路径压缩和按秩合并,单次操作均摊 — 反阿克曼函数,实际 ,基本就是 。

直觉 — 每个集合一棵树

想象一群人,每人指向自己的”老大”。问 “A 和 B 是不是一伙的?”,就各自沿着老大指针往上爬,爬到指向自己的人 (帮主/根) 为止。两人帮主相同 → 同一伙。要合并两个帮派,就让一个帮主认另一个当老大。整个数据结构只有一个数组 parent[i] = i 的父亲,根节点满足 parent[i] == i。

两个原语:

  • find(x): 沿父指针往上找,返回 x 所在集合的根。
  • union(x, y): 找到两个根 rx、ry,如果不同就让 parent[rx] = ry。

朴素版本最坏会退化成一条链,find 变 。两个优化救场:

  • 路径压缩: find 在回溯时把路径上每个节点直接挂到根上,树越用越扁。
  • 按秩合并: 矮树挂高树下,防止链化。

两者一起用,单次操作均摊 。

动画 — 看树长出来,看路径被压扁

下面动画依次执行 5 次 union 把 6 个节点连起来 (绿色 = 根),然后点击 执行 Find 观察路径压缩瞬间把所有节点拉到根下面 — 树从有层级直接拍扁成一层。

重点观察: union 之前每个节点都是自己的根;union 中根挂到根;Find 之后整棵树几乎只剩两层。

模板 — 路径压缩版 (90% 题够用)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class UnionFind:
    def __init__(self, n):
        self.p = list(range(n))     # parent[i] 初始指向自己
        self.cnt = n                # 连通分量个数

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])   # 路径压缩
        return self.p[x]

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False            # 已经同集合
        self.p[rx] = ry
        self.cnt -= 1
        return True

    def connected(self, x, y):
        return self.find(x) == self.find(y)

三个易错点:

  1. union 要先 find 两个根再合并,不能直接 p[x] = y — 那是把节点挂上去,会把原集合的其他节点甩掉。只有根代表整个集合。
  2. 路径压缩写在 find 里,不要忘。递归版最简洁,迭代版稍快、不爆栈。
  3. cnt 只在真正合并 (rx != ry) 时才减 1。

进阶 — 按秩合并 / 带权并查集

按秩合并

记每棵树的”秩” (粗略的高度),小树挂大树:

1
2
3
4
5
6
7
8
9
10
11
12
13
def __init__(self, n):
    self.p = list(range(n))
    self.r = [0] * n            # rank

def union(self, x, y):
    rx, ry = self.find(x), self.find(y)
    if rx == ry: return False
    if self.r[rx] < self.r[ry]:
        rx, ry = ry, rx         # 保证 rx 是高的
    self.p[ry] = rx
    if self.r[rx] == self.r[ry]:
        self.r[rx] += 1
    return True

实战里路径压缩一个就够。秩只有在严格证明复杂度、或题目卡常时才加。

带权并查集

核心一句话:每个节点不只记”父亲是谁”,还记一条”我和父亲之间的关系”(边权)。沿路径把这些关系叠起来,就得到任意两点之间的关系。 把 w[x] 想成一个从 x 指向父亲的”向量”,x 到根的关系 = 路径上一串向量首尾相接叠加。

多存一个数组 w[x] = x 到 p[x] 这条边的权。权值要能沿路径叠加,最常见两种模型:

  • 差值模型: ,沿路径用加法叠。
  • 比值模型 (LC 399): ,沿路径用乘法叠。

下面用差值模型讲透,比值只是把 + 换成 ×、0 换成 1。

find — 边找根,边把”到父亲”改成”到根”

1
2
3
4
5
6
def find(self, x):
    if self.p[x] != x:
        root = self.find(self.p[x])        # ① 先递归,让 p[x] 的 w 变成「p[x]→根」
        self.w[x] += self.w[self.p[x]]     # ② 「x→p[x]」+「p[x]→根」=「x→根」
        self.p[x] = root                   # ③ 再压缩,x 直接挂到根
    return self.p[x]

这三行顺序是死的: ①必须先递归(返回时 w[p[x]] 已是”父亲到根”); ②必须在③之前(还要用旧的 p[x],先改 p[x]=root 就丢了旧父亲)。

union — 用已知关系反推根到根的边权

find 之后我们手上有 、。把 挂到 下,新边权要满足不变量 。由 、 代入:

(最后一步用了 ,故 。)

查询 — 两条”到根向量”相减

同根时根被消掉: 。

完整模板 (差值版)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class WeightedUnionFind:
    def __init__(self, n):
        self.p = list(range(n))
        self.w = [0] * n            # w[x] = x 到父亲的差值;find 后变成 x 到根的差值

    def find(self, x):
        if self.p[x] != x:
            root = self.find(self.p[x])
            self.w[x] += self.w[self.p[x]]
            self.p[x] = root
        return self.p[x]

    def union(self, x, y, d):       # 录入:val[x] - val[y] = d
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return self.w[x] - self.w[y] == d   # 同集合:返回是否与已知一致(判矛盾)
        self.p[ry] = rx
        self.w[ry] = self.w[x] - self.w[y] - d  # 维持「子-父」不变量
        return True

    def diff(self, x, y):           # 查询 val[x] - val[y]
        if self.find(x) != self.find(y):
            return None             # 不连通 → 关系未知
        return self.w[x] - self.w[y]

方向不是由 d 决定的: “谁挂谁”是你自由定的(或按秩合并时按树大小定),d 只决定边权的数值。但全局必须统一 w 的语义(比如统一”子 − 父”);每次 union 谁当子,就让它满足这个语义即可,因此翻转挂接方向公式正好取反号。

比值模型 (LC 399 除法求值)

约定 ,find 后 。union(x,y,d) 录入 ,把 挂 下,需 。由 、 代入:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class RatioUnionFind:
    def __init__(self):
        self.p, self.w = {}, {}     # w[x] = val[x] / val[父]

    def add(self, x):
        if x not in self.p:
            self.p[x], self.w[x] = x, 1.0

    def find(self, x):
        if self.p[x] != x:
            root = self.find(self.p[x])
            self.w[x] *= self.w[self.p[x]]       # 连乘
            self.p[x] = root
        return self.p[x]

    def union(self, x, y, d):       # val[x] / val[y] = d
        self.add(x); self.add(y)
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return
        self.p[ry] = rx
        self.w[ry] = self.w[x] / (self.w[y] * d) # 维持「子/父」不变量

    def ratio(self, x, y):          # 查询 val[x] / val[y]
        if x not in self.p or y not in self.p or self.find(x) != self.find(y):
            return -1.0             # 不可达
        return self.w[x] / self.w[y]

两个模型对照,一眼记住规律——比值就是把差值的”减/加”换成”除/乘”:

模型 约定 union 边权公式
差值 父
比值 父

经典题: LC 399. 除法求值 — a/b = 2, b/c = 3 推 a/c,把”比值”当边权,find 时连乘。

三类场景 — 判连通 / 数分量 / 离线时光倒流

1. 判连通: 两点 find 同根 → 连通。冗余连接 (LC 684) 就是边一条条加,撞上同根的就是多余的。

2. 数连通分量: 最后 uf.cnt 就是答案。省份数量 (LC 547)、岛屿数量 (LC 200) 直接套。

3. 离线”时光倒流”: 并查集只支持合并,不支持拆分。题目要你删边/拆点?读完所有操作,从最终状态倒着加边就行 — 删变加。经典题 LC 803. 打砖块。

第三类是面试出”难题”的钥匙,看到”按顺序删除”先想能不能离线倒着做。

经典题

热身 (会一个会一类):

进阶:

记忆法

一句话: 集合即树,根即代表;find 找根,union 接根。

三件事必背:

项目 要点
数据 parent[] 一维数组,根满足 p[i]==i
find 沿父指针上爬到根,回溯时挂根 (路径压缩)
union 先 find 两个根,根挂根,cnt -= 1

判题口诀:

  • “几个连通块 / 是不是同一组” → 并查集
  • “按顺序加边” → 在线并查集
  • “按顺序删边 / 删点” → 离线倒着加 + 并查集
  • 边有权 (比值、差) → 带权并查集

模板背到能 30 秒默写出来,90% 的连通性题就是套模板 + 想清楚”节点是什么、什么时候 union”。