并查集：连通性的利器

第十五章：并查集 — 连通性的利器

你有一张城市地图，上面有几百个城市和若干条公路。现在有人问你："城市 A 和城市 B 之间有没有路可以到达？" 如果你对每次查询都跑一遍 BFS/DFS，复杂度是 O(V+E)。但如果这样的查询有一百万次呢？

并查集（Union-Find / Disjoint Set Union） 就是为了解决这类问题而生的数据结构。它支持两个核心操作：

1. Find(x)：找到 x 所属的集合（的代表元素）
2. Union(x, y)：将 x 和 y 所在的集合合并

经过路径压缩和按秩合并两个优化后，这两个操作的均摊时间复杂度是 O(α(n))，其中 α 是反阿克曼函数——一个增长极其缓慢的函数，对于所有实际可能的输入 n（哪怕 n = 宇宙中原子数量），α(n) ≤ 4。也就是说，并查集的每次操作几乎是常数时间。

这一章我们会从最朴素的实现开始，逐步加入优化，理解它为什么这么快，然后把它应用到图论和面试题中。

Level 1 · 你需要知道的

15.1 问题的起点：动态连通性

考虑这样一个场景：你管理一个社交网络，用户之间可以建立好友关系。你需要频繁回答这个问题——"用户 A 和用户 B 是否在同一个朋友圈里？"（不要求直接好友，间接连通也算）

更抽象地说，我们有 n 个元素，初始时每个元素自成一个集合。我们需要支持：

• 合并（Union）：把两个集合合并成一个
• 查询（Find）：判断两个元素是否在同一个集合中

这就是动态连通性问题（Dynamic Connectivity Problem）。

用数组标记连通分量？可以，但合并两个集合需要遍历整个数组改标记，O(n)。用邻接表建图 + BFS？可以，但每次查询 O(V+E)。并查集的优雅之处在于：它用一种极其简洁的树形结构，把这两个操作都做到了近乎 O(1)。

15.2 核心思想：用树表示集合

并查集的核心思想很简单：

• 每个集合用一棵树来表示
• 树的根节点就是这个集合的代表元素（representative）
• 判断两个元素是否在同一集合 = 判断它们的根是否相同
• 合并两个集合 = 把一棵树的根指向另一棵树的根

我们用一个数组 parent[] 来表示这些树：parent[i] 记录节点 i 的父节点。如果 parent[i] == i，说明 i 是根节点。

15.3 最朴素的实现

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))  # 初始时每个元素的父节点是自己
    
    def find(self, x):
        """找到 x 的根节点"""
        while self.parent[x] != x:
            x = self.parent[x]
        return x
    
    def union(self, x, y):
        """合并 x 和 y 所在的集合"""
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            self.parent[root_x] = root_y  # 把 x 的根挂到 y 的根下面
    
    def connected(self, x, y):
        """判断 x 和 y 是否在同一集合"""
        return self.find(x) == self.find(y)

问题在哪？ 这个朴素版本可能退化成链表！如果你依次执行 union(0,1), union(1,2), union(2,3), ...，树的高度变成 O(n)，每次 find 就是 O(n)。

15.4 优化一：路径压缩（Path Compression）

路径压缩的想法是：既然我们只关心根是谁，那在 find 的过程中，顺手把路径上的所有节点直接挂到根下面。这样下次再查这些节点，一步就能到根。

def find(self, x):
    """带路径压缩的 find"""
    if self.parent[x] != x:
        self.parent[x] = self.find(self.parent[x])  # 递归地把 x 直接连到根
    return self.parent[x]

一行递归就完成了路径压缩。执行完之后，x 到根之间的所有节点都直接指向了根。

如果你担心递归栈溢出（Python 的递归深度有限制），可以用迭代版本：

def find(self, x):
    """迭代版路径压缩"""
    root = x
    while self.parent[root] != root:
        root = self.parent[root]
    # 路径压缩：把 x 到 root 路径上的所有节点直接指向 root
    while self.parent[x] != root:
        next_x = self.parent[x]
        self.parent[x] = root
        x = next_x
    return root

15.5 优化二：按秩合并（Union by Rank）

路径压缩已经很强了，但我们还可以在 union 操作上做优化：合并时，总是把矮的树挂到高的树下面，这样合并后树的高度不会增加。

这里的"高度"我们用 rank 来近似（路径压缩会改变实际高度，但 rank 只在合并时更新，是高度的上界）。

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n  # rank[i] 是以 i 为根的树的高度上界
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False  # 已经在同一集合
        # 按秩合并：矮树挂到高树下面
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1  # 只有秩相同时，合并后秩才加 1
        return True
    
    def connected(self, x, y):
        return self.find(x) == self.find(y)

为什么只有秩相同时才加 1？ 因为高度为 h 的树至少有 2^h 个节点（归纳可证）。如果两棵高度不同的树合并，把矮的挂到高的下面，高度不变。只有两棵同高度的树合并时，高度才会加 1。

15.6 完整实现：带连通分量计数

在很多应用场景中，我们还需要知道"一共有多少个不同的连通分量"。只需要维护一个计数器，每次成功合并就减 1：

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n  # 初始时有 n 个连通分量
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
        self.count -= 1  # 合并成功，连通分量数减 1
        return True
    
    def connected(self, x, y):
        return self.find(x) == self.find(y)
    
    def get_count(self):
        return self.count

15.7 使用示例

# 5 个节点，编号 0-4
uf = UnionFind(5)
print(uf.get_count())  # 5，每个节点各自一个分量

uf.union(0, 1)  # {0,1}, {2}, {3}, {4}
uf.union(2, 3)  # {0,1}, {2,3}, {4}
print(uf.get_count())  # 3

print(uf.connected(0, 1))  # True
print(uf.connected(0, 2))  # False

uf.union(1, 3)  # {0,1,2,3}, {4}
print(uf.connected(0, 2))  # True
print(uf.get_count())  # 2

15.8 按大小合并（Union by Size）的变体

有时候我们需要知道每个连通分量的大小。这种情况下用"按大小合并"代替"按秩合并"更自然：

class UnionFindBySize:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n  # size[i] = 以 i 为根的集合大小
        self.count = n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False
        # 小集合挂到大集合下面
        if self.size[root_x] < self.size[root_y]:
            self.parent[root_x] = root_y
            self.size[root_y] += self.size[root_x]
        else:
            self.parent[root_y] = root_x
            self.size[root_x] += self.size[root_y]
        self.count -= 1
        return True
    
    def get_size(self, x):
        return self.size[self.find(x)]

按大小合并和按秩合并的时间复杂度是一样的，都是 O(α(n))。区别在于按大小合并能在 O(1) 时间内回答"这个集合有多大"的问题。

15.9 并查集 vs 其他方案的对比

α(n) ≤ 4 对所有实际输入，所以最后一行实质上是 O(1)。

15.10 什么时候用并查集

并查集适合的场景特征：

1. 只需要判断连通性，不需要具体路径
2. 动态添加边（只加不删——标准并查集不支持删除操作）
3. 离线处理或在线查询都可以
4. 需要高效合并集合

不适合的场景：

• 需要找最短路径 → 用 BFS/Dijkstra
• 需要删除边 → 用 Link-Cut Tree 或离线逆序处理
• 需要遍历某个集合的所有元素 → 并查集没有直接支持这个操作

Level 2 · 它是怎么运行的

15.11 复杂度分析：为什么近乎 O(1)

只用路径压缩

如果只使用路径压缩（不用按秩/按大小合并），m 次操作的总时间是 O(m log n)，均摊每次 O(log n)。

直觉：路径压缩让树越来越"扁"。一开始 find 可能走很长的路径，但它同时把路径上所有节点都直接连到根了，后续的 find 操作就变快了。这是一种典型的"均摊分析"——偶尔做一次昂贵操作，为后续操作省下大量时间。

只用按秩合并

如果只使用按秩合并（不用路径压缩），树的高度保证是 O(log n)。

证明：归纳法。rank 为 r 的树至少有 2^r 个节点。

• 基础：rank = 0，树只有根，1 = 2^0 节点 ✓
• 归纳：rank 为 r 的树只能通过合并两棵 rank 为 r-1 的树产生。由归纳假设，每棵至少 2^(r-1) 个节点，合并后至少 2^(r-1) + 2^(r-1) = 2^r 个节点 ✓

因此 rank ≤ log₂(n)，find 操作是 O(log n)。

路径压缩 + 按秩合并

当两个优化同时使用时，m 次操作的总时间是 O(m · α(n))，其中 α 是反阿克曼函数（Inverse Ackermann Function）。

15.12 反阿克曼函数 α(n)

阿克曼函数 A(m, n) 是一个增长极快的函数：

A(0, n) = n + 1
A(m, 0) = A(m-1, 1)                     (m > 0)
A(m, n) = A(m-1, A(m, n-1))             (m > 0, n > 0)

看几个值：

• A(1, n) = n + 2
• A(2, n) = 2n + 3
• A(3, n) = 2^(n+3) - 3
• A(4, 1) = 2^(2^(2^(65536))) - 3 —— 一个天文数字
• A(4, 2) —— 已经无法写下来了

反阿克曼函数 α(n) = min{k : A(k, k) ≥ n}。由于 A 增长极快，α 增长极慢：

由于宇宙中的原子数约为 10^80 ≈ 2^265，远小于 2^65536 = A(4,1)，所以对所有实际输入，α(n) ≤ 4。

这意味着什么？ 路径压缩 + 按秩合并的并查集，每次操作最多需要 4 步额外工作（在均摊意义下）。这就是为什么我们说它"几乎是 O(1)"。

15.13 Tarjan 证明的核心思想

Robert Tarjan 在 1975 年证明了 O(m · α(n)) 的上界。他的证明思路（大幅简化版）：

1. 定义一个势能函数 Φ，基于树中每个节点的"层级"
2. 将节点按 rank 分成若干"块"，块的大小按阿克曼函数递增
3. 证明：路径压缩操作要么减少势能（为后续操作"存钱"），要么自己的实际代价很小
4. 通过势能法的均摊分析，得到总代价 O(m · α(n))

下界方面，Fredman 和 Saks（1989）证明了：在 cell-probe 模型下，任何支持 Union 和 Find 的数据结构，m 次操作的最坏情况时间都不可能比 O(m · α(n)) 更好。也就是说，路径压缩 + 按秩合并是渐近最优的。

15.14 带权并查集（Weighted Union-Find）

标准并查集只能回答"两个元素是否在同一集合"。但有些问题需要维护元素之间的相对关系（比如相对距离、相对大小）。带权并查集就是为此设计的。

核心思想：在 parent 数组之外，再维护一个 weight 数组。weight[x] 表示 x 到 parent[x] 的"距离"（或其他关系值）。通过 find 路径上的权重累加，可以得到任意节点到根的总权重。

class WeightedUnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.weight = [0] * n  # weight[x] = x 到 parent[x] 的权重
    
    def find(self, x):
        """返回 x 的根，同时做路径压缩并更新权重"""
        if self.parent[x] != x:
            root = self.find(self.parent[x])
            self.weight[x] += self.weight[self.parent[x]]  # 累加路径上的权重
            self.parent[x] = root
        return self.parent[x]
    
    def union(self, x, y, w):
        """
        合并 x 和 y，且 weight(x) - weight(y) = w
        即 x 相对于 y 的权重差是 w
        """
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return  # 已经在同一集合，可以检查一致性
        # w(x→root_x) 已知 = self.weight[x]（find 之后）
        # w(y→root_y) 已知 = self.weight[y]（find 之后）
        # 我们要让 root_x → root_y，权重为 w + w(y→root_y) - w(x→root_x)
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
            self.weight[root_x] = w + self.weight[y] - self.weight[x]
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
            self.weight[root_y] = -w + self.weight[x] - self.weight[y]
        else:
            self.parent[root_x] = root_y
            self.weight[root_x] = w + self.weight[y] - self.weight[x]
            self.rank[root_y] += 1
    
    def query(self, x, y):
        """查询 weight(x) - weight(y)，前提是 x 和 y 在同一集合"""
        if self.find(x) != self.find(y):
            return None  # 不在同一集合，无法比较
        return self.weight[x] - self.weight[y]

带权并查集的典型应用：

• LeetCode 399 - 除法求值：已知 a/b = 2, b/c = 3，求 a/c。把除法关系建模为权重：weight(a) / weight(b) = 2，用乘法权重的并查集。
• 食物链问题（NOI 2001）：三种动物 A、B、C 形成食物链 A 吃 B、B 吃 C、C 吃 A。用权重 mod 3 表示相对关系。

15.15 Kruskal 最小生成树算法

并查集最经典的图论应用是 Kruskal 算法——找最小生成树（Minimum Spanning Tree）。

算法思想：

1. 把所有边按权重从小到大排序
2. 依次考虑每条边 (u, v, w)：如果 u 和 v 不在同一连通分量，加入这条边（合并 u 和 v）
3. 重复直到加入了 n-1 条边（n 是节点数）

def kruskal(n, edges):
    """
    n: 节点数
    edges: [(weight, u, v), ...]
    返回最小生成树的边列表和总权重
    """
    edges.sort()  # 按权重排序
    uf = UnionFind(n)
    mst = []
    total_weight = 0
    
    for weight, u, v in edges:
        if not uf.connected(u, v):
            uf.union(u, v)
            mst.append((u, v, weight))
            total_weight += weight
            if len(mst) == n - 1:
                break  # 已经找到 n-1 条边，生成树完成
    
    return mst, total_weight

时间复杂度：排序 O(E log E) + 遍历所有边做 Union/Find O(E · α(V))。总计 O(E log E)，因为排序是瓶颈。

为什么 Kruskal 是正确的？ 这是贪心算法的经典应用。其正确性由**割的性质（Cut Property）**保证：对于图的任意一个割（把节点分成两组），跨越这个割的最小权重边一定属于某棵最小生成树。Kruskal 每次加入一条边时，它恰好是当前连接两个不同连通分量的最小权重边——这正是割的性质的应用。

关于最小生成树的更深入讨论，请参见第 18 章。

15.16 路径压缩的几种变体

除了完全路径压缩（所有节点直接连到根），还有几种变体：

路径分裂（Path Splitting）：把路径上每个节点指向它的祖父节点。

def find_path_splitting(self, x):
    while self.parent[x] != x:
        self.parent[x], x = self.parent[self.parent[x]], self.parent[x]
    return x

路径减半（Path Halving）：每隔一个节点指向祖父。

def find_path_halving(self, x):
    while self.parent[x] != x:
        self.parent[x] = self.parent[self.parent[x]]
        x = self.parent[x]
    return x

这三种变体（完全压缩、路径分裂、路径减半）在理论上具有相同的 O(m · α(n)) 均摊复杂度。在实践中，路径减半通常最快，因为它只修改一半的指针，减少了内存写操作。

15.17 并查集的空间优化

对于节点编号连续的情况，并查集只需要两个数组（parent 和 rank/size），空间是严格的 O(n)。

但如果节点不是连续整数（比如是字符串），我们可以用哈希表来代替数组：

class UnionFindMap:
    def __init__(self):
        self.parent = {}
        self.rank = {}
    
    def add(self, x):
        if x not in self.parent:
            self.parent[x] = x
            self.rank[x] = 0
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        self.add(x)
        self.add(y)
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
        return True

Level 3 · 规范怎么定义的

15.18 历史：Galler 和 Fischer 的 1964 年论文

并查集的发明可以追溯到 Bernard A. Galler 和 Michael J. Fischer 在 1964 年发表的论文 "An Improved Equivalence Algorithm"（发表在 Communications of the ACM, Vol. 7, No. 5, pp. 301-303）。

他们的动机来自 FORTRAN 编译器中的等价声明（EQUIVALENCE statement）。FORTRAN 的 EQUIVALENCE 语句允许程序员声明两个变量共享同一块内存。编译器需要维护这种等价关系的传递闭包——如果 A 等价于 B，B 等价于 C，那么 A 也等价于 C。

Galler 和 Fischer 提出了用树来表示等价类的方法，并引入了按大小合并（union by size） 的优化。他们证明了对 n 个元素的 m 次操作，总时间是 O(m log n)。这在当时已经是一个巨大的改进——之前的方法是 O(mn) 的。

原文引用（Galler & Fischer, 1964）：

"The improved algorithm which we describe here represents each class of equivalent identifiers as a tree structure, where the root of each tree serves as the canonical representative of its class."

这是计算机科学史上最简洁、最优雅的数据结构发明之一：总共只有两页纸，核心代码不超过 20 行，却解决了一个实际且重要的问题。

15.19 Tarjan 的 1975 年突破

Robert Endre Tarjan（是的，就是发明 Tarjan 强连通分量算法的那位）在 1975 年发表了划时代的论文 "Efficiency of a Good But Not Linear Set Union Algorithm"（Journal of the ACM, Vol. 22, No. 2, pp. 215-225）。

Tarjan 的贡献：

1. 引入路径压缩：虽然路径压缩的想法在此前已被使用，Tarjan 首次对它进行了严格的复杂度分析。

2. 证明了 O(m · α(n)) 的上界：这是一个惊人的结果。之前人们知道按秩合并给出 O(m log n)，知道路径压缩在实践中很快，但没有人能证明两者结合到底有多快。Tarjan 使用了精巧的势能方法，定义了一个基于阿克曼函数的分层结构来完成证明。

3. 猜想这是最优的：Tarjan 猜测 O(m · α(n)) 是最优的，但当时无法证明下界。

证明的关键工具——阿克曼函数：Tarjan 选择阿克曼函数不是偶然的。他的分析需要一个增长极快的函数来"分层"——把节点的 rank 分成越来越大的块。阿克曼函数的超指数增长恰好提供了正确的分层粒度。

15.20 下界证明：Fredman-Saks 1989

Michael Fredman 和 Michael Saks 在 1989 年的论文 "The Cell Probe Complexity of Dynamic Data Structures"（Proceedings of STOC, pp. 345-354）中证明了：

在 cell-probe 模型下，任何支持 m 次 Union-Find 操作的数据结构，最坏情况下至少需要 Ω(m · α(n)) 时间。

这意味着并查集（路径压缩 + 按秩合并）是渐近最优的——你不可能发明一个在最坏情况下比它更快的数据结构来解决动态连通性问题。

cell-probe 模型是一个非常强的计算模型（只计算内存访问次数，计算本身免费），所以在这个模型下的下界也适用于所有更弱的计算模型（包括 RAM 模型）。

15.21 并查集在 Percolation 中的应用

渗流（Percolation） 是统计物理学中的经典模型，也是并查集的一个优美应用。

问题描述：有一个 n×n 的网格，每个格子以概率 p 是"开放的"（可通过），以概率 1-p 是"封闭的"。问：从顶部到底部是否存在一条连通路径？

关键概念——渗流阈值：存在一个临界概率 p* ≈ 0.5927（对于二维方格格点），当 p > p* 时，几乎一定能从顶部到达底部；当 p < p* 时，几乎一定不能。这是一个相变（phase transition） 现象。

用并查集解决：

import random

class Percolation:
    def __init__(self, n):
        self.n = n
        self.grid = [[False] * n for _ in range(n)]
        # n*n 个格子 + 2 个虚拟节点（顶部源、底部汇）
        self.uf = UnionFind(n * n + 2)
        self.top = n * n      # 虚拟顶部节点
        self.bottom = n * n + 1  # 虚拟底部节点
        self.open_count = 0
    
    def _index(self, row, col):
        return row * self.n + col
    
    def open(self, row, col):
        if self.grid[row][col]:
            return
        self.grid[row][col] = True
        self.open_count += 1
        
        # 如果在第一行，连接到虚拟顶部
        if row == 0:
            self.uf.union(self._index(row, col), self.top)
        # 如果在最后一行，连接到虚拟底部
        if row == self.n - 1:
            self.uf.union(self._index(row, col), self.bottom)
        
        # 连接相邻的开放格子
        for dr, dc in [(-1,0), (1,0), (0,-1), (0,1)]:
            nr, nc = row + dr, col + dc
            if 0 <= nr < self.n and 0 <= nc < self.n and self.grid[nr][nc]:
                self.uf.union(self._index(row, col), self._index(nr, nc))
    
    def percolates(self):
        """从顶部到底部是否连通"""
        return self.uf.connected(self.top, self.bottom)


def estimate_threshold(n, trials=1000):
    """蒙特卡洛估计渗流阈值"""
    total = 0
    for _ in range(trials):
        perc = Percolation(n)
        sites = [(r, c) for r in range(n) for c in range(n)]
        random.shuffle(sites)
        for r, c in sites:
            perc.open(r, c)
            if perc.percolates():
                total += perc.open_count / (n * n)
                break
    return total / trials

这个算法由 Princeton 的 Robert Sedgewick 教授用作 Algorithms 课程的经典编程作业。它精美地展示了并查集如何在模拟科学实验中发挥作用——每打开一个格子，做常数次 union 操作即可，整个模拟只需要 O(n² · α(n²)) 时间。

15.22 并查集的学术变体

带回滚的并查集（Rollback Union-Find / Persistent Union-Find）：

标准并查集的合并是不可逆的。但在某些算法中（如分治算法处理边的删除问题），我们需要"撤销"上一次合并。按秩合并（不做路径压缩）时，可以用栈记录每次修改，需要回滚时逆序恢复。

class RollbackUnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.history = []  # 记录所有修改
    
    def find(self, x):
        # 注意：不能做路径压缩！否则无法回滚
        while self.parent[x] != x:
            x = self.parent[x]
        return x
    
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            self.history.append(None)  # 标记：这次没有实际合并
            return False
        if self.rank[root_x] < self.rank[root_y]:
            root_x, root_y = root_y, root_x
        # 记录修改前的状态
        self.history.append((root_y, self.parent[root_y], root_x, self.rank[root_x]))
        self.parent[root_y] = root_x
        if self.rank[root_x] == self.rank[root_y]:
            self.rank[root_x] += 1
        return True
    
    def rollback(self):
        """撤销最近一次 union 操作"""
        record = self.history.pop()
        if record is None:
            return  # 那次 union 没有实际合并
        root_y, old_parent, root_x, old_rank = record
        self.parent[root_y] = old_parent
        self.rank[root_x] = old_rank

注意，带回滚的并查集不能使用路径压缩（否则一次 find 可能修改很多节点，无法简单回滚），所以它的复杂度是 O(log n) 而非 O(α(n))。

离线删边问题：如果问题涉及删边，一个常用技巧是"时间逆序"——把删边变成加边，然后用标准并查集从后往前处理。这避免了使用复杂的可持久化数据结构。

15.23 并查集与其他数据结构的关系

与图的 BFS/DFS 的关系：并查集可以看作图连通性查询的"预处理"。如果边集是固定的，一次 DFS 标记连通分量 O(V+E) 就够了。并查集的优势在于边集是动态变化的——新边不断加入。

与最小生成树的关系：Kruskal 算法用并查集，Prim 算法用优先队列。两者时间复杂度相近，但 Kruskal 更适合稀疏图（E 接近 V），Prim 更适合稠密图（E 接近 V²）。

与 Link-Cut Tree 的关系：并查集只支持合并，不支持分裂。Link-Cut Tree（Sleator & Tarjan, 1983）支持动态连接和断开，但每次操作 O(log n)，常数更大。如果不需要删除操作，并查集是更好的选择。

Level 4 · 边界与陷阱

15.24 面试题一：省份数量（LeetCode 547）

题目：有 n 个城市，isConnected[i][j] = 1 表示城市 i 和城市 j 直接相连。求省份数量（连通分量个数）。

分析：这是并查集最直接的应用——遍历所有边，合并连通的城市，最后返回连通分量数。

def findCircleNum(isConnected):
    n = len(isConnected)
    uf = UnionFind(n)
    
    for i in range(n):
        for j in range(i + 1, n):  # 只遍历上三角
            if isConnected[i][j] == 1:
                uf.union(i, j)
    
    return uf.get_count()

时间复杂度：O(n² · α(n))，遍历邻接矩阵。 空间复杂度：O(n)。

常见错误：

1. 忘记只遍历上三角（或下三角），导致重复处理。不影响正确性但浪费时间。
2. 忘记 isConnected[i][i] = 1 不需要处理（自己和自己当然连通）。

替代解法：DFS/BFS 也能解这题，遍历每个未访问的节点，做一次 DFS 标记整个连通分量。时间一样是 O(n²)，但并查集的优势在于代码更简洁，且如果后续要动态加边更灵活。

15.25 面试题二：冗余连接（LeetCode 684）

题目：一棵树加了一条多余的边变成了图。找到这条多余的边（如果有多个答案，返回输入中最后出现的那条）。

分析：树有 n 个节点和 n-1 条边。题目给 n 条边（多了一条），找到加入后会形成环的那条边。

关键洞察：按输入顺序逐条加边，第一条"两端已经连通"的边就是形成环的边。由于题目要求返回"最后出现的"，而我们是按顺序遍历的，所以最后一条导致环的边就是答案。

等等，题目保证只有一条多余的边，所以只有一条边会导致环。

def findRedundantConnection(edges):
    n = len(edges)
    uf = UnionFind(n + 1)  # 节点编号从 1 开始
    
    for u, v in edges:
        if not uf.union(u, v):
            return [u, v]  # 这条边的两端已经连通，它就是多余的
    
    return []  # 不会到这里

为什么这是正确的？ 树的定义是无环连通图。按顺序加边，前面的边构成森林（无环）。当加入一条边 (u, v) 时，如果 u 和 v 已经在同一棵树里，这条边就形成了环——它就是多余的。

面试追问：如果是有向图呢？（LeetCode 685 - 冗余连接 II）这就复杂很多了，需要分情况讨论：是否有节点入度为 2，是否形成有向环。

15.26 面试题三：等式方程的可满足性（LeetCode 990）

题目：给定一组等式和不等式（如 ["a==b", "b!=c", "c==a"]），判断是否存在满足所有约束的赋值。

分析：

• 等式 a==b 意味着 a 和 b 必须在同一集合
• 不等式 a!=b 意味着 a 和 b 必须在不同集合

策略：先处理所有等式（union），再检查所有不等式是否冲突。

def equationsPossible(equations):
    uf = UnionFind(26)  # 26 个字母
    
    # 第一遍：处理所有等式
    for eq in equations:
        if eq[1] == '=':  # "x==y"
            x = ord(eq[0]) - ord('a')
            y = ord(eq[3]) - ord('a')
            uf.union(x, y)
    
    # 第二遍：检查所有不等式
    for eq in equations:
        if eq[1] == '!':  # "x!=y"
            x = ord(eq[0]) - ord('a')
            y = ord(eq[3]) - ord('a')
            if uf.connected(x, y):
                return False  # 矛盾！x 和 y 已经在同一集合了
    
    return True

为什么先处理等式再处理不等式？ 因为等式具有传递性（a==b, b==c → a==c），我们需要先把所有传递关系建立起来，然后再检查不等式是否与这些关系矛盾。如果交替处理，可能漏掉传递关系。

面试追问：如果不等式也有传递性呢？（比如类似约束满足问题）那就不能用简单的并查集了，需要用 2-SAT 或约束传播。

15.27 面试题四：按公因数连接（LeetCode 952）

题目：给定数组 nums，如果 nums[i] 和 nums[j] 有大于 1 的公因数，就把它们连一条边。求最大连通分量的大小。

暴力分析：两两检查 GCD，O(n² log(max))，太慢。

优化思路：不对每对数字做 GCD，而是对每个数字做因式分解，把数字和它的因子放在同一集合。

def largestComponentSize(nums):
    max_val = max(nums)
    uf = UnionFind(max_val + 1)
    
    for num in nums:
        # 对 num 做因式分解，把 num 和所有因子合并
        d = 2
        while d * d <= num:
            if num % d == 0:
                uf.union(num, d)
                uf.union(num, num // d)
            d += 1
    
    # 统计每个连通分量中有多少个 nums 中的数
    from collections import Counter
    count = Counter(uf.find(num) for num in nums)
    return max(count.values())

为什么这是正确的？ 如果 nums[i] 和 nums[j] 有公因子 p，那么 nums[i] 和 p 在同一集合，nums[j] 和 p 也在同一集合，所以 nums[i] 和 nums[j] 在同一集合。传递性自动由并查集保证。

时间复杂度：每个数字的因式分解是 O(√num)，总共 O(n · √max_val)。远好于 O(n²)。

空间优化：上面的实现创建了 max_val + 1 大小的 UnionFind，如果 nums 中的数很大但个数少，可以用哈希表版本。

面试追问：如果数据范围到 10^9 怎么办？预处理质因数用线性筛（Sieve），或者只对 nums 中的数做分解并用映射压缩。

15.28 并查集的常见陷阱

陷阱 1：忘记对 find 返回值操作

# 错误！
if uf.parent[x] == uf.parent[y]:  # 这比较的是直接父节点，不是根！
    ...

# 正确
if uf.find(x) == uf.find(y):
    ...

陷阱 2：合并的是原始节点而不是根

# 错误！
def union(self, x, y):
    self.parent[x] = y  # 直接把 x 连到 y，破坏了树结构

# 正确
def union(self, x, y):
    root_x = self.find(x)
    root_y = self.find(y)
    self.parent[root_x] = root_y  # 连接的是根

陷阱 3：节点编号从 1 开始但数组从 0 开始

很多图论题节点编号从 1 到 n，创建 UnionFind 时要用 n + 1 大小，或者把所有编号减 1。

陷阱 4：Python 递归深度

Python 默认递归深度是 1000。如果树很深（比如 10^5 个节点的链状树，路径压缩前第一次 find），递归版会爆栈。解决方案：

• 用迭代版 find
• 或者 import sys; sys.setrecursionlimit(200000)（不推荐，可能真的栈溢出）

陷阱 5：误以为并查集能高效处理删边

并查集只支持合并，不支持分裂。如果题目有删边操作，要么：

• 离线逆序处理（把删边变成加边）
• 用 Link-Cut Tree
• 用带回滚的并查集 + 分治

15.29 并查集在面试中的识别模式

当你在面试中遇到以下关键词或模式时，考虑并查集：

面试时的模板：

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry: return False
        if self.rank[rx] < self.rank[ry]: rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]: self.rank[rx] += 1
        self.count -= 1
        return True
    
    def connected(self, x, y):
        return self.find(x) == self.find(y)

这个模板大约 20 行代码，面试时 2 分钟内应该能默写出来。建议多练几次直到肌肉记忆。

15.30 综合对比与总结

一句话总结：并查集是解决动态连通性问题的最优数据结构——O(α(n)) 近乎常数的时间复杂度、O(n) 的空间、20 行的代码量，三者兼得。它的局限是只支持合并不支持分裂、只能判断连通性不能给出路径。在面试中，一旦识别出"动态合并 + 连通性查询"的模式，并查集就是你的首选武器。