并查集

1. 概述与学习目标

1.1 什么是并查集

并查集（Disjoint Set Union, DSU；又称 Union-Find）是一种维护不相交集合族的数据结构，支持以下两类核心操作：

• 查找（Find）：给定元素 $x$，返回 $x$ 所在集合的代表元（root），用于判断两个元素是否属于同一集合；
• 合并（Union）：给定两个元素 $x, y$，将它们所在的集合合并为一个集合。

并查集以森林（forest）表示集合族：每个集合对应一棵树，树根即为集合代表元。借助路径压缩与按秩合并两项优化，$m$ 次操作在 $n$ 个元素上的总代价为 $O(m \cdot \alpha(n))$，其中 $\alpha(n)$ 是反 Ackermann 函数，增长极慢，对所有实际可能出现的 $n$（$n \leq 10^{80}$，即可观测宇宙原子数）均有 $\alpha(n) \leq 4$，故可视为常数。

一句话定义：并查集 = 不相交集合森林 + 路径压缩 + 按秩合并，均摊 $O(\alpha(n))$ ≈ $O(1)$，最坏 $O(\log n)$。

1.2 学习目标

完成本文档学习后，你将能够：

1. 记忆并查集作为不相交集合森林的形式化定义，复述 find / union / connected 三种操作的均摊 $O(\alpha(n))$ 复杂度结论；
2. 理解 Galler-Fischer 1964 早期形式化与 Tarjan 1975 给出 $O(m \cdot \alpha(n))$ 上界的历史脉络，说明反 Ackermann 函数为何”对所有实际问题可视为常数”；
3. 应用路径压缩与按秩合并两种优化，针对动态连通性、最小生成树、连通分量统计编写可运行的 Python/C++/Java 代码；
4. 分析 Ackermann 函数 $A(m, n)$ 与其反函数 $\alpha(n)$ 的定义，论证 $m$ 次 find 操作在 $n$ 个元素上的总代价为 $O(m \cdot \alpha(n))$ 的均摊上界；
5. 评估并查集相对于哈希集合、树状数组、线段树在”动态连通性”问题维度上的优劣，识别其在 Kruskal / Tarjan 离线 LCA / 网络连通判定中的选型动机；
6. 对比朴素 union、按秩合并、按大小合并、路径压缩（递归/迭代）、双优化结合等变体在最坏与均摊复杂度维度的差异；
7. 创造性设计基于并查集的开源项目解决方案，如社交网络关系聚类、最小生成树并行构建、游戏内连通区域判定。

1.3 适用场景与不适用场景

跨模块引用：并查集在 Kruskal 算法中的应用详见 图算法；与树状数组的复杂度对比详见 树状数组。

2. 历史动机与演进

2.1 前并查集时代：等价关系的朴素处理

1960 年代初期，编译器设计领域遇到等价关系判定问题：Fortran 中的 EQUIVALENCE 语句声明若干变量共享内存，编译器需要计算等价类的闭包。例如：

EQUIVALENCE (A, B), (B, C), (D, E)

意味着 A、B、C 共享同一内存位置，D、E 共享另一内存位置。朴素方法用二维布尔矩阵维护传递闭包，空间 $O(n^2)$、合并 $O(n)$，对大型程序不可接受。

2.2 Galler-Fischer 1964：树形表示的诞生

1964 年，密歇根大学 Bernard A. Galler 与 Michael J. Fischer 在 Communications of the ACM 7(5): 301-303 发表论文《An improved equivalence algorithm》，首次提出用森林表示等价类：

• 每个元素是一个节点；
• 同一等价类的节点通过父指针连接成一棵树；
• 树根作为等价类的代表元；
• 合并两个等价类即将一棵树的根挂到另一棵的根下。

这一表示将合并操作降至 $O(1)$，但查找最坏 $O(n)$（退化为链）。论文未给出严格的均摊分析，但奠定了现代并查集的雏形。

2.3 Hopcroft-Ullman 1973：路径压缩与 $O(m \log^* n)$ 上界

1973 年，康奈尔大学 John E. Hopcroft 与 Jeffrey D. Ullman 在 SIAM Journal on Computing 2(4): 294-303 发表《Set merging algorithms》，引入路径压缩（path compression）优化，并证明 $m$ 次操作在 $n$ 个元素上的总代价为 $O(m \log^* n)$，其中 $\log^* n$ 是重对数函数（iterated logarithm）：

$\log^* n = \min \{ k \geq 0 : \log^{(k)} n \leq 1 \}$

其中 $\log^{(k)}$ 表示连续应用 $k$ 次对数。$\log^* n$ 增长极慢（$\log^* 2^{65536} = 5$），在当时被视为”近线性”突破。

教学提示：Hopcroft 与 Ullman 因此工作成为算法分析的奠基者之一。Hopcroft 于 1986 年与 Robert Tarjan 共享图灵奖”for fundamental achievements in the design and analysis of algorithms and data structures”。

2.4 Tarjan 1975：反 Ackermann 函数的精确上界

1975 年，加州大学伯克利分校 Robert Endre Tarjan（当时在康奈尔）在 Journal of the ACM 22(2): 215-225 发表论文《Efficiency of a good but not linear set union algorithm》，证明：

定理（Tarjan 1975）：对路径压缩与按秩合并结合的并查集，$m$ 次操作在 $n$ 个元素上的总代价为 $\Theta(m \cdot \alpha(m, n))$，其中 $\alpha$ 是 Ackermann 函数的反函数。

论文标题中的 “good but not linear” 反映了一个深刻的事实：

• “good”：$\alpha(n)$ 增长极慢，对所有实际 $n$ 不超过 4，“实际线性”；
• “not linear”：严格数学意义上，$\alpha(n) \to \infty$（$n \to \infty$），并非真正线性。

Tarjan 同时证明：任何基于指针的 DSU 实现都存在 $\Omega(m \cdot \alpha(m, n))$ 的下界，意味着这一复杂度是最优的。

2.5 演进时间线

timeline
    title 并查集演进时间线
    1928 : Ackermann 提出快速函数 A(m,n) (Hilbert 学生)
    1964 : Galler-Fischer 树形表示 (CACM)
    1973 : Hopcroft-Ullman 引入路径压缩, O(m log* n)
    1975 : Tarjan 给出 O(m α(n)) 精确上界 (JACM)
    1983 : Tarjan 出版 Data Structures and Network Algorithms
    1985 : Tarjan 系统化均摊分析 (SIAM J. Algebraic Discrete Methods)
    1986 : Hopcroft 与 Tarjan 共享图灵奖
    1989 : CLRS 第 1 版收录 DSU (Chapter 22)
    2006 : Kleinberg-Tardos Algorithm Design 收录 DSU 应用
    2011 : Sedgewick-Wayne Algorithms 第 4 版 1.5 节 Case Study
    2022 : CLRS 第 4 版将 DSU 移至第 21 章

2.6 关键设计决策

并查集演进过程中有四个关键设计决策：

1. 树形而非矩阵表示：Galler-Fischer 选择父指针树，将空间从 $O(n^2)$ 降至 $O(n)$，代价是查找从 $O(1)$ 升至 $O(n)$（无优化时）；
2. 路径压缩而非旋转：Hopcroft-Ullman 选择”查找时扁平化”，而非平衡树的旋转操作，因为 DSU 不需要维护严格顺序；
3. 按秩而非按大小合并：Tarjan 证明按秩合并与路径压缩结合可达到 $\alpha(n)$ 下界；按大小合并同样可达此下界，但常数略大；
4. 均摊而非最坏分析：单次 find 最坏仍 $O(\log n)$，但 $m$ 次操作均摊 $O(\alpha(n))$。这是均摊分析方法的奠基性应用。

教学提示：理解并查集演进的关键是抓住”用随机/均摊代替严格平衡”的思想。这与跳跃表用概率平衡、哈希表用平均情况分析一脉相承。

3. 形式化定义

3.1 不相交集合族

定义 3.1（不相交集合族）：设 $U$ 是有限全集合，$S_1, S_2, \ldots, S_k \subseteq U$ 是 $U$ 的子集族。称 $\{S_1, \ldots, S_k\}$ 是不相交集合族（disjoint set family），若满足：

1. 两两不相交：$\forall i \neq j, S_i \cap S_j = \emptyset$；
2. 并集为 $U$：$\bigcup_{i=1}^{k} S_i = U$（有时放宽为 $\subseteq U$，允许部分元素未初始化）。

每个 $S_i$ 称为一个等价类或连通分量。

3.2 操作的形式化定义

并查集维护以下三种操作：

1. MAKE-SET($x$)：创建一个仅包含 $x$ 的新集合 $\{x\}$，前置条件 $x$ 之前不在任何集合中；
2. FIND($x$)：返回包含 $x$ 的集合的代表元（root）；
3. UNION($x, y$)：将包含 $x$ 与 $y$ 的两个不同集合合并为一个集合。

正确性不变量：

• 任意时刻，所有集合构成 $U$ 的一个划分（partition）；
• $\text{FIND}(x) = \text{FIND}(y) \iff x$ 与 $y$ 在同一集合中。

3.3 森林表示

并查集以不相交集合森林（disjoint-set forest）实现：

• 每个元素 $x$ 对应一个节点；
• 每个节点维护 parent[x] 指针，指向父节点；
• 根节点 parent[r] = r（自指），作为集合代表元；
• 每棵树对应一个集合，树的形态无关紧要，仅需根标识集合。

FIND($x$)：沿 parent 指针上行至根。

UNION($x, y$)：先 FIND 两个根 $r_x, r_y$，若不同则将一棵挂到另一棵下（parent[r_x] = r_y 或反之）。

3.4 Ackermann 函数与反函数

定义 3.2（Ackermann 函数）：Wilhelm Ackermann 1928 年提出的二元递归函数 $A: \mathbb{N} \times \mathbb{N} \to \mathbb{N}$：

该函数增长极快：

定义 3.3（反 Ackermann 函数）：

$\alpha(m, n) = \min \{ k \geq 0 : A(k, \lfloor m/n \rfloor) > \log_2 n \}$

当 $m \geq n$ 时简化为单参数形式：

$\alpha(n) = \min \{ k \geq 0 : A(k, k) > \log_2 n \}$

实际意义：

• $\alpha(0) = 0$；
• $\alpha(1) = 0$；
• $\alpha(2) = 1$；
• $\alpha(4) = 2$；
• $\alpha(16) = 3$；
• $\alpha(2^{65536}) = 4$；
• $\alpha(2^{2^{65536}}) = 5$；
• 对所有 $n \leq 10^{80}$（可观测宇宙原子数估计），$\alpha(n) \leq 4$。

3.5 Tarjan 定理

定理 3.1（Tarjan 1975）：对由路径压缩与按秩合并结合实现的并查集，$m$ 次 MAKE-SET / FIND / UNION 操作（其中 $n$ 次 MAKE-SET）的总时间复杂度为：

$T(m, n) = \Theta(m \cdot \alpha(m, n))$

且任何基于指针比较的 DSU 实现都存在 $\Omega(m \cdot \alpha(m, n))$ 的下界。

推论 3.1：当 $m \geq n$ 时，单次操作的均摊复杂度为 $\Theta(\alpha(n))$，对所有实际 $n$ 不超过 4，可视为 $O(1)$ 常数。

教学提示：Tarjan 定理的证明涉及势能方法（potential method）与等级分层（rank stratification），完整证明约 15 页，详见 Tarjan 1983 著作 Data Structures and Network Algorithms 第 2 章。本文档仅给出直观说明，完整证明在延伸阅读中给出参考。

4. 数据结构与基本操作

4.1 节点结构

并查集节点需要存储：

• parent：父节点指针，根节点指向自身；
• rank（可选）：树高度的上界估计，用于按秩合并；
• size（可选）：集合大小，用于按大小合并。

# Python 实现：并查集节点
from typing import Optional


class DSUNode:
    """并查集节点。

    Attributes:
        value: 节点存储的值（元素标识）
        parent: 父节点指针，根节点指向自身
        rank: 树高度的上界估计，仅根节点的 rank 有意义
        size: 该节点为根时集合的大小
    """

    __slots__ = ('value', 'parent', 'rank', 'size')

    def __init__(self, value):
        self.value = value
        self.parent: Optional['DSUNode'] = self  # 初始自指，即自身为根
        self.rank: int = 0
        self.size: int = 1

    def is_root(self) -> bool:
        """判断是否为根节点"""
        return self.parent is self

    def __repr__(self) -> str:
        return f"DSUNode(value={self.value!r}, rank={self.rank}, size={self.size})"

// C++ 实现：并查集节点
template<typename T>
struct DSUNode {
    T value;                  // 元素值
    DSUNode<T>* parent;       // 父指针，根节点指向自身
    int rank;                 // 树高度上界估计
    int size;                 // 集合大小（仅根节点有效）

    DSUNode(const T& v)
        : value(v), parent(this), rank(0), size(1) {}

    bool is_root() const { return parent == this; }
};

// Java 实现：并查集节点
public class DSUNode<T> {
    final T value;
    DSUNode<T> parent;   // 父指针，根节点指向自身
    int rank;            // 树高度上界估计
    int size;            // 集合大小（仅根节点有效）

    public DSUNode(T value) {
        this.value = value;
        this.parent = this;  // 初始自指，即自身为根
        this.rank = 0;
        this.size = 1;
    }

    public boolean isRoot() {
        return parent == this;
    }
}

4.2 数组表示（工程常用）

工程实践中，元素常以整数 $0, 1, \ldots, n-1$ 编号，此时用数组替代节点对象可减少内存开销并提升缓存友好性：

class UnionFind:
    """数组实现的并查集。

    用两个数组分别存储父指针与秩（或大小），
    避免对象开销，缓存友好，适合元素为连续整数的场景。

    Attributes:
        parent: parent[i] 表示元素 i 的父节点编号
        rank: rank[i] 表示以 i 为根的树的高度上界
        size: size[i] 表示以 i 为根的集合大小
        count: 当前集合数量（连通分量数）
    """

    def __init__(self, n: int):
        """初始化 n 个独立集合，每个元素自成一类。

        Args:
            n: 元素总数，编号 0 到 n-1
        """
        self.parent = list(range(n))   # parent[i] = i 初始自指
        self.rank = [0] * n            # 初始 rank 均为 0
        self.size = [1] * n            # 初始每个集合大小为 1
        self.count = n                 # 初始有 n 个集合

    def __len__(self) -> int:
        """返回元素总数"""
        return len(self.parent)

    @property
    def components(self) -> int:
        """返回当前连通分量数"""
        return self.count

// C++ 实现：数组并查集
#include <vector>

class UnionFind {
private:
    std::vector<int> parent_;
    std::vector<int> rank_;
    std::vector<int> size_;
    int count_;   // 连通分量数

public:
    // 构造函数：初始化 n 个独立集合
    explicit UnionFind(int n)
        : parent_(n), rank_(n, 0), size_(n, 1), count_(n) {
        for (int i = 0; i < n; ++i) {
            parent_[i] = i;
        }
    }

    int count() const { return count_; }
    int size() const { return static_cast<int>(parent_.size()); }
};

// Java 实现：数组并查集
public class UnionFind {
    private final int[] parent;
    private final int[] rank;
    private final int[] size;
    private int count;   // 连通分量数

    /**
     * 初始化 n 个独立集合。
     *
     * @param n 元素总数，编号 0 到 n-1
     */
    public UnionFind(int n) {
        this.parent = new int[n];
        this.rank = new int[n];
        this.size = new int[n];
        this.count = n;
        for (int i = 0; i < n; i++) {
            parent[i] = i;   // 初始自指
            rank[i] = 0;
            size[i] = 1;
        }
    }

    public int count() { return count; }
    public int size() { return parent.length; }
}

4.3 可视化示例

假设初始 8 个元素 {0,1,2,3,4,5,6,7}，执行以下操作：

union(1, 2):     1 <- 2           (1 为根)
union(3, 4):     3 <- 4
union(5, 6):     5 <- 6
union(1, 3):     1 <- 2
                 1 <- 3 <- 4
union(2, 6):     1 <- 2
                 1 <- 3 <- 4
                 1 <- 5 <- 6
最终森林:        {0} {1,2,3,4,5,6} {7}
find(4) = 1
find(6) = 1
connected(4, 6) = true

森林形态（树高 2，按秩合并未触发）：

        1
      / | \
     2  3  5
        |  |
        4  6

5. 核心操作实现

5.1 朴素 Find（无路径压缩）

def find(self, x: int) -> int:
    """查找元素 x 的根节点（无路径压缩）。

    Time Complexity: O(n) 最坏（退化为链）
                     O(h) 一般，h 为树高

    Args:
        x: 元素编号

    Returns:
        根节点编号
    """
    while self.parent[x] != x:
        x = self.parent[x]
    return x

// C++ 朴素 find
int find(int x) {
    while (parent_[x] != x) {
        x = parent_[x];
    }
    return x;
}

// Java 朴素 find
public int find(int x) {
    while (parent[x] != x) {
        x = parent[x];
    }
    return x;
}

5.2 朴素 Union（无按秩合并）

def union(self, x: int, y: int) -> bool:
    """合并 x 与 y 所在的集合（无按秩合并）。

    Time Complexity: O(n) 最坏（依赖 find）

    Args:
        x: 元素编号
        y: 元素编号

    Returns:
        True 表示合并成功，False 表示原本就在同一集合
    """
    root_x = self.find(x)
    root_y = self.find(y)
    if root_x == root_y:
        return False
    # 简单地将 r_x 挂到 r_y 下，可能导致链化
    self.parent[root_x] = root_y
    self.count -= 1
    return True

问题：朴素 union 容易导致树退化为链，使 find 退化为 $O(n)$。

5.3 路径压缩（Path Compression）

路径压缩在 find 操作中，将查找路径上的所有节点直接挂到根节点，从而扁平化树结构。

def find(self, x: int) -> int:
    """查找 + 路径压缩（递归实现）。

    递归找到根后，将当前节点的父指针直接指向根。
    路径上所有节点都会被压缩到根。

    Time Complexity: O(α(n)) 均摊（结合按秩合并）
                     O(log n) 最坏单次

    Args:
        x: 元素编号

    Returns:
        根节点编号
    """
    if self.parent[x] != x:
        # 递归找根，并将当前节点直接挂到根
        self.parent[x] = self.find(self.parent[x])
    return self.parent[x]

def find_iterative(self, x: int) -> int:
    """查找 + 路径压缩（迭代实现，避免栈溢出）。

    两遍扫描：
    1. 第一遍：沿父指针上行找到根
    2. 第二遍：将路径上所有节点的父指针改为根

    适合处理大规模数据，避免递归栈深度限制。

    Args:
        x: 元素编号

    Returns:
        根节点编号
    """
    # 第一遍：找根
    root = x
    while self.parent[root] != root:
        root = self.parent[root]
    # 第二遍：压缩路径
    while self.parent[x] != root:
        next_node = self.parent[x]
        self.parent[x] = root
        x = next_node
    return root

// C++ 路径压缩（递归）
int find(int x) {
    if (parent_[x] != x) {
        parent_[x] = find(parent_[x]);   // 递归压缩
    }
    return parent_[x];
}

// C++ 路径压缩（迭代）
int find_iterative(int x) {
    int root = x;
    while (parent_[root] != root) {
        root = parent_[root];
    }
    while (parent_[x] != root) {
        int next = parent_[x];
        parent_[x] = root;
        x = next;
    }
    return root;
}

// Java 路径压缩（递归）
public int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);   // 递归压缩
    }
    return parent[x];
}

// Java 路径压缩（迭代）
public int findIterative(int x) {
    int root = x;
    while (parent[root] != root) {
        root = parent[root];
    }
    while (parent[x] != root) {
        int next = parent[x];
        parent[x] = root;
        x = next;
    }
    return root;
}

压缩效果示意：

压缩前:       1 <- 2 <- 3 <- 4 <- 5 <- 6    (find(6))
压缩后:       1 <- 2
              1 <- 3
              1 <- 4
              1 <- 5
              1 <- 6
              (路径上所有节点直接挂到根 1)

5.4 路径分裂（Path Splitting）

路径分裂是路径压缩的轻量变体：遍历路径时，将每个节点的父指针改为祖父节点。

def find_path_splitting(self, x: int) -> int:
    """路径分裂：每个节点父指针改为祖父节点。

    相比路径压缩，路径分裂只需一遍扫描，常数更小，
    但均摊复杂度仍为 O(α(n))（结合按秩合并）。

    Args:
        x: 元素编号

    Returns:
        根节点编号
    """
    while self.parent[x] != x:
        # 将 x 的父指针改为祖父，然后跳到原父节点
        next_node = self.parent[x]
        self.parent[x] = self.parent[next_node] if self.parent[next_node] != next_node else next_node
        x = next_node
    return x

5.5 路径减半（Path Halving）

路径减半是另一轻量变体：每隔一个节点，将其父指针改为祖父。

def find_path_halving(self, x: int) -> int:
    """路径减半：每隔一个节点改为指向祖父。

    与路径分裂同属"就地压缩"变体，均摊复杂度仍为 O(α(n))。
    实现略简，但效果略弱于路径分裂。

    Args:
        x: 元素编号

    Returns:
        根节点编号
    """
    while self.parent[x] != x:
        if self.parent[self.parent[x]] != self.parent[x]:
            # 将 x 的父指针改为祖父
            self.parent[x] = self.parent[self.parent[x]]
        x = self.parent[x]
    return x

5.6 按秩合并（Union by Rank）

按秩合并：始终将较小秩的树挂到较大秩的树下，保证树高增长缓慢。

def union_by_rank(self, x: int, y: int) -> bool:
    """按秩合并：较小秩挂到较大秩下。

    性质：合并后树高至多 max(rank_x, rank_y)，
          当且仅当 rank_x == rank_y 时树高增加 1。

    Time Complexity: O(α(n)) 均摊（结合路径压缩）

    Args:
        x: 元素编号
        y: 元素编号

    Returns:
        True 表示合并成功，False 表示原本就在同一集合
    """
    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
        self.size[root_y] += self.size[root_x]
    elif self.rank[root_x] > self.rank[root_y]:
        self.parent[root_y] = root_x
        self.size[root_x] += self.size[root_y]
    else:
        # 秩相等：任选一个作根，根的 rank 加 1
        self.parent[root_y] = root_x
        self.rank[root_x] += 1
        self.size[root_x] += self.size[root_y]

    self.count -= 1
    return True

// C++ 按秩合并
bool unionByRank(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX == rootY) return false;

    if (rank_[rootX] < rank_[rootY]) {
        parent_[rootX] = rootY;
        size_[rootY] += size_[rootX];
    } else if (rank_[rootX] > rank_[rootY]) {
        parent_[rootY] = rootX;
        size_[rootX] += size_[rootY];
    } else {
        parent_[rootY] = rootX;
        rank_[rootX]++;
        size_[rootX] += size_[rootY];
    }
    count_--;
    return true;
}

// Java 按秩合并
public boolean unionByRank(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX == rootY) return false;

    if (rank[rootX] < rank[rootY]) {
        parent[rootX] = rootY;
        size[rootY] += size[rootX];
    } else if (rank[rootX] > rank[rootY]) {
        parent[rootY] = rootX;
        size[rootX] += size[rootY];
    } else {
        parent[rootY] = rootX;
        rank[rootX]++;
        size[rootX] += size[rootY];
    }
    count--;
    return true;
}

5.7 按大小合并（Union by Size）

按大小合并：始终将较小集合挂到较大集合下。这一变体在实践中常用，因为 size 字段同时支持查询集合大小。

def union_by_size(self, x: int, y: int) -> bool:
    """按大小合并：较小集合挂到较大集合下。

    性质：合并后树高至多 log2(n)，因为每次合并较小集合大小至少翻倍。
    这保证了不依赖路径压缩时 find 也是 O(log n)。

    Time Complexity: O(α(n)) 均摊（结合路径压缩）

    Args:
        x: 元素编号
        y: 元素编号

    Returns:
        True 表示合并成功，False 表示原本就在同一集合
    """
    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]:
        root_x, root_y = root_y, root_x   # 交换，确保 root_x 是较大者
    self.parent[root_y] = root_x
    self.size[root_x] += self.size[root_y]

    self.count -= 1
    return True

5.8 Connected 查询

def connected(self, x: int, y: int) -> bool:
    """判断 x 与 y 是否在同一集合。

    Time Complexity: O(α(n)) 均摊

    Args:
        x: 元素编号
        y: 元素编号

    Returns:
        True 表示在同一集合，False 表示不在
    """
    return self.find(x) == self.find(y)

5.9 完整实现

class UnionFind:
    """完整的并查集实现（路径压缩 + 按秩合并）。

    均摊复杂度 O(α(n))，对所有实际 n 可视为 O(1)。
    """

    def __init__(self, n: int):
        """初始化 n 个独立集合。

        Args:
            n: 元素总数，编号 0 到 n-1
        """
        self.parent = list(range(n))
        self.rank = [0] * n
        self.size = [1] * n
        self.count = n

    def find(self, x: int) -> int:
        """查找 + 路径压缩（递归）"""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x: int, y: int) -> bool:
        """按秩合并"""
        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
            self.size[root_y] += self.size[root_x]
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
            self.size[root_x] += self.size[root_y]
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
            self.size[root_x] += self.size[root_y]
        self.count -= 1
        return True

    def connected(self, x: int, y: int) -> bool:
        """判断连通性"""
        return self.find(x) == self.find(y)

    def get_size(self, x: int) -> int:
        """查询 x 所在集合大小"""
        return self.size[self.find(x)]

    def __len__(self) -> int:
        return len(self.parent)

    @property
    def components(self) -> int:
        """连通分量数"""
        return self.count

// C++ 完整实现
#include <vector>

class UnionFind {
private:
    std::vector<int> parent_;
    std::vector<int> rank_;
    std::vector<int> size_;
    int count_;

public:
    explicit UnionFind(int n)
        : parent_(n), rank_(n, 0), size_(n, 1), count_(n) {
        for (int i = 0; i < n; ++i) parent_[i] = i;
    }

    int find(int x) {
        if (parent_[x] != x) {
            parent_[x] = find(parent_[x]);
        }
        return parent_[x];
    }

    bool unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;
        if (rank_[rx] < rank_[ry]) {
            parent_[rx] = ry;
            size_[ry] += size_[rx];
        } else if (rank_[rx] > rank_[ry]) {
            parent_[ry] = rx;
            size_[rx] += size_[ry];
        } else {
            parent_[ry] = rx;
            rank_[rx]++;
            size_[rx] += size_[ry];
        }
        count_--;
        return true;
    }

    bool connected(int x, int y) { return find(x) == find(y); }
    int getSize(int x) { return size_[find(x)]; }
    int count() const { return count_; }
    int size() const { return static_cast<int>(parent_.size()); }
};

// Java 完整实现
public class UnionFind {
    private final int[] parent;
    private final int[] rank;
    private final int[] size;
    private int count;

    public UnionFind(int n) {
        this.parent = new int[n];
        this.rank = new int[n];
        this.size = new int[n];
        this.count = n;
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
            size[i] = 1;
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    public boolean union(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;
        if (rank[rx] < rank[ry]) {
            parent[rx] = ry;
            size[ry] += size[rx];
        } else if (rank[rx] > rank[ry]) {
            parent[ry] = rx;
            size[rx] += size[ry];
        } else {
            parent[ry] = rx;
            rank[rx]++;
            size[rx] += size[ry];
        }
        count--;
        return true;
    }

    public boolean connected(int x, int y) { return find(x) == find(y); }
    public int getSize(int x) { return size[find(x)]; }
    public int count() { return count; }
    public int size() { return parent.length; }
}

6. 复杂度分析

6.1 各优化组合的复杂度对比

6.2 仅按秩合并的 $O(\log n)$ 证明

引理 6.1：仅按秩合并（无路径压缩）时，rank 为 $k$ 的根节点至少有 $2^k$ 个后代。

证明（数学归纳法）：

• 基础：初始 rank = 0，节点自身即 1 = $2^0$ 个后代；
• 归纳：rank 从 $k$ 升到 $k+1$ 仅发生在两个 rank $k$ 的根合并时，新根有 $2^k + 2^k = 2^{k+1}$ 个后代。

推论 6.1：树高 $h \leq \log_2 n$，故 find 为 $O(\log n)$。

6.3 仅路径压缩的 $O(\log n)$ 均摊证明

仅路径压缩（无按秩合并）时，分析更为复杂。Tarjan 1975 证明单次 find 均摊为 $O(\log n)$，但总操作复杂度为 $O(m \log n)$。

6.4 双优化结合的 $O(\alpha(n))$ 证明（直观说明）

完整证明涉及势能方法与等级分层，约 15 页。这里给出直观思路：

关键思想：定义节点的”等级”（level）为其 rank 的分段函数：

$\text{level}(x) = \max \{ k : \text{rank}(x) \geq A(k, \text{rank}(\text{parent}(x))) \}$

等级取值范围为 $\{0, 1, \ldots, \alpha(n)\}$。可以证明：

1. 路径压缩每次将节点 $x$ 的父指针改为更”高”等级的节点；
2. 每个节点的等级单调不减，至多为 $\alpha(n)$；
3. 等级 $k$ 的节点至多被压缩 $2^{A(k, \cdot)}$ 次。

总操作数求和后得到 $O(m \cdot \alpha(n))$ 上界。

详细证明参见 Tarjan 1983 Data Structures and Network Algorithms 第 2 章，或 CLRS 第 4 版第 21 章。

6.5 反 Ackermann 函数的数值直观

可观测宇宙原子数约 $10^{80} \approx 2^{266}$，对应 $\alpha \approx 4$。这意味着对任何实际问题，$\alpha(n) \leq 4$，DSU 操作可视为 $O(1)$。

7. 变体与增强

7.1 带权并查集

带权并查集（Weighted Union-Find）在每个节点上额外维护到根的权值，支持”关系判断”类问题。

class WeightedUnionFind:
    """带权并查集。

    维护每个节点到根的"权值"（距离），支持查询两节点间的相对权值。
    常用于：食物链、关系判断、差分约束等场景。

    Attributes:
        parent: 父指针
        rank: 树高度上界
        weight: weight[i] 表示节点 i 到其父节点的权值（路径压缩后改为到根）
    """

    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.weight = [0] * n   # 初始每个节点到自身的权值为 0

    def find(self, x: int) -> int:
        """查找 + 路径压缩，同时维护 weight[x] 为 x 到根的权值"""
        if self.parent[x] != x:
            root = self.find(self.parent[x])
            # 路径压缩前，weight[x] 是 x 到原父的权值
            # 父节点已压缩，weight[parent[x]] 是父到根的权值
            # 所以 x 到根的权值 = weight[x] + weight[parent[x]]
            self.weight[x] += self.weight[self.parent[x]]
            self.parent[x] = root
        return self.parent[x]

    def union(self, x: int, y: int, w: int) -> bool:
        """合并：x 到 y 的权值为 w（即 weight[x] - weight[y] = w）。

        Args:
            x: 元素编号
            y: 元素编号
            w: x 相对 y 的权值差

        Returns:
            True 表示合并成功，False 表示原本在同一集合
        """
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False
        # 现有：weight[x] 是 x 到 root_x 的权值
        #       weight[y] 是 y 到 root_y 的权值
        # 要求：weight[x] - weight[y] = w
        # 将 root_x 挂到 root_y 下，则 root_x 到 root_y 的权值应为：
        #   weight[y] + w - weight[x]
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
            self.weight[root_x] = self.weight[y] + w - self.weight[x]
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
            self.weight[root_y] = self.weight[x] - w - self.weight[y]
        else:
            self.parent[root_x] = root_y
            self.rank[root_y] += 1
            self.weight[root_x] = self.weight[y] + w - self.weight[x]
        return True

    def diff(self, x: int, y: int) -> int:
        """查询 x 相对 y 的权值差（需先 ensure same set）"""
        if self.find(x) != self.find(y):
            raise ValueError("x and y are not in the same set")
        return self.weight[x] - self.weight[y]

应用示例：食物链问题（POJ 1182）。三种动物 A、B、C 形成”A 吃 B、B 吃 C、C 吃 A”的食物链，给定若干陈述 “x 吃 y” 或 “x 与 y 同类”，判断哪些陈述是假话。

7.2 可撤销并查集

可撤销并查集（Rollback Union-Find）不支持路径压缩（因为压缩会破坏历史信息），但支持回滚到之前的状态。

class RollbackUnionFind:
    """可撤销并查集（无路径压缩，按秩合并）。

    用栈记录每次 union 的修改，支持回滚到之前的状态。
    不使用路径压缩，保证单次 find 为 O(log n)。

    应用场景：动态图连通性（离线）、回溯算法中维护连通性。
    """

    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.history = []   # 操作历史栈，存储 (root_x, root_y, rank_y_old)

    def find(self, x: int) -> int:
        """朴素 find（无路径压缩）"""
        while self.parent[x] != x:
            x = self.parent[x]
        return x

    def union(self, x: int, y: int) -> bool:
        """按秩合并，并记录历史"""
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            self.history.append((root_x, root_y, -1))   # -1 标记未实际合并
            return False
        if self.rank[root_x] < self.rank[root_y]:
            root_x, root_y = root_y, root_x
        # root_x 是较大者，root_y 挂到 root_x 下
        old_rank = self.rank[root_x]
        self.parent[root_y] = root_x
        if self.rank[root_x] == self.rank[root_y]:
            self.rank[root_x] += 1
        self.history.append((root_x, root_y, old_rank))
        return True

    def rollback(self) -> bool:
        """撤销最近一次 union 操作。

        Returns:
            True 表示撤销成功，False 表示历史为空
        """
        if not self.history:
            return False
        root_x, root_y, old_rank = self.history.pop()
        if old_rank == -1:
            return True   # 未实际合并，无需撤销
        self.parent[root_y] = root_y   # 恢复 root_y 为根
        self.rank[root_x] = old_rank   # 恢复 rank
        return True

7.3 持久化并查集

持久化并查集（Persistent Union-Find）支持查询历史版本。实现思路：用函数式持久化平衡树（如 Treap）替代 parent 数组，每次修改产生新版本。复杂度 $O(\log n \log n)$。

7.4 动态连通性（完全）

完全动态连通性（支持删除边）需要更复杂的数据结构，如欧拉回路树（Euler Tour Tree）或Holm-de Lichtenberg-Thorup（HDT）算法，达到 $O(\log^2 n)$ 单次操作。

8. 对比分析

8.1 与其他数据结构的对比

8.2 与最小生成树算法的对比

8.3 与 LCA 算法的对比

9. 常见陷阱

9.1 陷阱 1：未初始化 parent 数组

错误代码：

class UnionFind:
    def __init__(self, n):
        self.parent = [0] * n   # 错误：所有元素指向 0

问题：所有元素的父指针都指向 0，导致 0 成为”伪根”，find 行为异常。

修正：

self.parent = list(range(n))   # 正确：parent[i] = i 初始自指

9.2 陷阱 2：递归 find 导致栈溢出

错误场景：当 $n = 10^7$ 且树退化为链时，递归深度达 $10^7$，Python 默认递归深度限制 1000，触发 RecursionError。

修正：使用迭代版本，或在程序入口设置：

import sys
sys.setrecursionlimit(10 ** 7)

9.3 陷阱 3：按秩合并时未正确更新 rank

错误代码：

def union(self, x, y):
    root_x = self.find(x)
    root_y = self.find(y)
    if root_x == root_y:
        return False
    self.parent[root_x] = root_y
    self.rank[root_y] += 1   # 错误：每次合并都增加 rank
    return True

问题：每次合并都增加 rank，导致 rank 失去”高度上界”含义，可能远超实际高度。

修正：仅在两树 rank 相等时增加新根的 rank：

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   # 仅此时增加

9.4 陷阱 4：路径压缩与按秩合并的”假矛盾”

误解：路径压缩会改变树高，使 rank 失去意义，因此两者不能共存。

真相：路径压缩后，rank 不再是高度的精确值，但仍是高度的上界。Tarjan 1975 证明这足以保证均摊 $O(\alpha(n))$ 复杂度。CLRS 第 21 章明确指出：“Although path compression can change the height of a tree, it does not affect the rank of any node.”

9.5 陷阱 5：忘记维护 count（连通分量数）

错误：union 成功后未更新 self.count，导致查询连通分量数时返回错误值。

修正：在 union 成功分支末尾添加：

self.count -= 1

9.6 陷阱 6：在 find 中调用 union 导致递归

错误代码：

def find(self, x):
    if self.parent[x] != x:
        self.union(self.parent[x], x)   # 错误：在 find 中调 union
        return self.find(x)
    return x

问题：union 内部又调 find，形成无限递归。

修正：find 中只修改 parent 指针，不调 union：

def find(self, x):
    if self.parent[x] != x:
        self.parent[x] = self.find(self.parent[x])
    return self.parent[x]

9.7 陷阱 7：负数元素编号

错误场景：LeetCode 题目中节点编号为 -1 到 -n，直接用数组下标访问导致越界。

修正：偏移映射，或用字典替代数组：

class UnionFindDict:
    """支持任意可哈希元素的并查集"""
    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):
        self.add(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
        return True

9.8 陷阱 8：在 Python 中误用 is 比较整数

错误代码：

if self.parent[x] is x:   # 错误：is 比较对象身份，非值
    return x

问题：Python 中 is 对小整数（-5 到 256）有效，但对大整数可能失效。

修正：始终用 ==：

if self.parent[x] == x:
    return x

10. 工程实践

10.1 性能基准测试

以下是 Python 实现在不同规模下的性能基准（M1 Pro, 16GB, Python 3.11）：

观察：双优化比朴素快约 100 倍，验证 $\alpha(n) \ll \log n$ 在实际中的差距。

10.2 工业级实现注意事项

1. 内存布局：用数组而非对象，提升缓存命中率；
2. 避免递归：大规模数据用迭代版 find，避免栈溢出；
3. 批量操作：若需批量 union，可先排序后处理；
4. 并发安全：标准 DSU 非线程安全，并发场景需加锁或用无锁版本；
5. 内存回收：C++ 中用 unique_ptr 管理节点内存，避免泄漏。

10.3 Redis 中的应用

Redis 集群使用 哈希槽（hash slot）分配键到节点，而非一致性哈希。虽然不直接使用 DSU，但在槽迁移过程中，DSU 的”动态合并”思想被借鉴：迁移中的槽同时属于”源节点”与”目标节点”，通过类似 DSU 的代表元机制确保查询一致性。

10.4 编译器中的应用

编译器中等价关系判定（如 Fortran EQUIVALENCE、C 联合体、类型别名）经典地使用 DSU：

// C 联合体示例
union { int i; float f; } u;
// i 和 f 共享内存，编译器内部用 DSU 维护等价类

LLVM 在 SSA 形式构建中使用 DSU 合并支配前沿的等价变量。

10.5 游戏开发中的应用

游戏地图中连通区域判定（如扫雷中的”展开”区域、俄罗斯方块中的”消行”判定）常用 DSU：

# 扫雷展开算法：BFS + DSU 加速
def expand_minesweeper(board, click_x, click_y):
    """点击空白格时展开连通区域"""
    rows, cols = len(board), len(board[0])
    uf = UnionFind(rows * cols)
    # 将所有空白格按相邻关系 union
    for i in range(rows):
        for j in range(cols):
            if board[i][j] == 0:   # 空白格
                for ni, nj in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
                    if 0 <= ni < rows and 0 <= nj < cols and board[ni][nj] == 0:
                        uf.union(i*cols + j, ni*cols + nj)
    # 展开与点击格连通的所有空白格
    root = uf.find(click_x * cols + click_y)
    for i in range(rows):
        for j in range(cols):
            if board[i][j] == 0 and uf.find(i*cols + j) == root:
                board[i][j] = -2   # 标记为已展开

11. 案例研究

11.1 案例一：Kruskal 最小生成树

问题：给定无向连通图 $G = (V, E)$，每条边 $e \in E$ 有权值 $w(e)$，求总权值最小的生成树。

算法：

1. 将所有边按权值升序排序；
2. 初始化 DSU，每个顶点自成一集合；
3. 依次考察每条边 $(u, v, w)$：
   • 若 $u, v$ 不在同一集合，加入 MST，并 union；
   • 否则跳过（避免成环）；
4. 当 MST 包含 $|V| - 1$ 条边时结束。

完整实现：

def kruskal(n: int, edges: list[tuple[int, int, int]]) -> tuple[list[tuple[int,int,int]], int]:
    """Kruskal 最小生成树算法。

    Args:
        n: 顶点数（编号 0 到 n-1）
        edges: 边列表，每条边为 (u, v, weight)

    Returns:
        (MST 边列表, 总权值)
    """
    # 按权值排序
    edges.sort(key=lambda e: e[2])
    uf = UnionFind(n)
    mst = []
    total = 0
    for u, v, w in edges:
        if uf.union(u, v):   # 不在同一集合，加入 MST
            mst.append((u, v, w))
            total += w
            if len(mst) == n - 1:
                break
    return mst, total


# 测试
edges = [
    (0, 1, 4), (0, 7, 8),
    (1, 2, 8), (1, 7, 11),
    (2, 3, 7), (2, 5, 4), (2, 8, 2),
    (3, 4, 9), (3, 5, 14),
    (4, 5, 10),
    (5, 6, 2),
    (6, 7, 1), (6, 8, 6),
    (7, 8, 7),
]
mst, total = kruskal(9, edges)
print(f"MST 边: {mst}")
print(f"总权值: {total}")
# 输出: MST 边: [(6,7,1), (2,8,2), (5,6,2), (0,1,4), (2,5,4), (2,3,7), (0,7,8), (3,4,9)]
#      总权值: 37

复杂度：$O(E \log E)$（排序主导），DSU 操作 $O(E \cdot \alpha(V))$ 可忽略。

11.2 案例二：省份数量（LeetCode 547）

问题：有 $n$ 个城市，给定 $n \times n$ 矩阵 isConnected，isConnected[i][j] = 1 表示城市 $i$ 与 $j$ 直接相连。省份是直接或间接相连的城市集合，求省份数量。

算法：DSU 合并所有相连城市，最终连通分量数即为省份数。

def findCircleNum(isConnected: list[list[int]]) -> int:
    """LeetCode 547: 省份数量"""
    n = len(isConnected)
    uf = UnionFind(n)
    for i in range(n):
        for j in range(i + 1, n):
            if isConnected[i][j]:
                uf.union(i, j)
    return uf.count


# 测试
assert findCircleNum([[1,1,0],[1,1,0],[0,0,1]]) == 2
assert findCircleNum([[1,0,0],[0,1,0],[0,0,1]]) == 3

11.3 案例三：冗余连接（LeetCode 684）

问题：给定无向图的边列表（$n$ 个节点，$n$ 条边，形成恰好一个环），删除一条边使图变为树。返回最后一条导致环的边。

算法：依次加入每条边，若 union 返回 False（已在同一集合），该边即为冗余。

def findRedundantConnection(edges: list[list[int]]) -> list[int]:
    """LeetCode 684: 冗余连接"""
    n = len(edges)
    uf = UnionFind(n + 1)   # 节点编号 1 到 n
    for u, v in edges:
        if not uf.union(u, v):   # 已连通，该边冗余
            return [u, v]
    return []


# 测试
assert findRedundantConnection([[1,2],[1,3],[2,3]]) == [2,3]
assert findRedundantConnection([[1,2],[2,3],[3,4],[1,4],[1,5]]) == [1,4]

11.4 案例四：岛屿数量（LeetCode 200）

问题：给定 $m \times n$ 二维网格，'1' 表示陆地，'0' 表示水域，相邻（上下左右）的陆地组成岛屿，求岛屿数量。

算法：DSU 合并所有相邻陆地，最终陆地集合数即为岛屿数。

def numIslands(grid: list[list[str]]) -> int:
    """LeetCode 200: 岛屿数量"""
    if not grid:
        return 0
    m, n = len(grid), len(grid[0])
    uf = UnionFind(m * n)
    water_count = 0

    for i in range(m):
        for j in range(n):
            if grid[i][j] == '0':
                water_count += 1
                continue
            # 仅向右、向下合并，避免重复
            for di, dj in [(0, 1), (1, 0)]:
                ni, nj = i + di, j + dj
                if ni < m and nj < n and grid[ni][nj] == '1':
                    uf.union(i * n + j, ni * n + nj)

    # 统计陆地中不同根的数量
    land_roots = set()
    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                land_roots.add(uf.find(i * n + j))
    return len(land_roots)


# 测试
grid = [
    ['1','1','0','0','0'],
    ['1','1','0','0','0'],
    ['0','0','1','0','0'],
    ['0','0','0','1','1'],
]
assert numIslands(grid) == 3

11.5 案例五：账户合并（LeetCode 721）

问题：给定账户列表 accounts[i] = [name, email1, email2, ...]，相同 email 视为同一账户。合并后返回去重后的账户列表。

算法：DSU 合并所有共享 email 的账户，按 email 而非账户索引建图。

from collections import defaultdict


def accountsMerge(accounts: list[list[str]]) -> list[list[str]]:
    """LeetCode 721: 账户合并"""
    email_to_id = {}   # email 到 DSU 编号的映射
    email_to_name = {}
    uid = 0

    # 第一遍：为每个 email 分配唯一 ID，记录 name
    for account in accounts:
        name = account[0]
        for email in account[1:]:
            if email not in email_to_id:
                email_to_id[email] = uid
                uid += 1
            email_to_name[email] = name

    uf = UnionFind(uid)

    # 第二遍：同一账户的所有 email 互相 union
    for account in accounts:
        first_email = account[1]
        for email in account[2:]:
            uf.union(email_to_id[first_email], email_to_id[email])

    # 第三遍：按根分组
    root_to_emails = defaultdict(list)
    for email, idx in email_to_id.items():
        root_to_emails[uf.find(idx)].append(email)

    # 输出结果
    result = []
    for emails in root_to_emails.values():
        emails.sort()
        name = email_to_name[emails[0]]
        result.append([name] + emails)
    return result

12. 习题与解答

12.1 选择题

题目 1（基础，easy）：路径压缩与按秩合并结合的并查集，单次 find 的均摊复杂度为？

• A. $O(1)$
• B. $O(\log n)$
• C. $O(\alpha(n))$
• D. $O(n)$

题目 2（中等，medium）：以下哪种优化组合能保证 find 的最坏复杂度为 $O(\log n)$？

• A. 仅路径压缩
• B. 仅按秩合并
• C. 路径压缩 + 按秩合并
• D. 朴素 union

题目 3（中等，medium）：Ackermann 函数 $A(2, 3)$ 的值为？

• A. 5
• B. 7
• C. 9
• D. 13