第 21 章 不相交集合

本章对应原书第 21 章。不相交集合（并查集，union-find）只做两件事：查一个元素属于哪一组，把两组合并成一组。结构极其简单——每个元素只存一个父指针和一个整数——却有着全书最精巧的摊还分析之一。它是下一章连通分量和第 23 章 Kruskal 最小生成树的核心部件。在量化里，凡是"按某种关联关系把股票、因子、证券标识归成若干组"的任务，几乎都可以用它一行一行地合并出来。

学习目标

读完本章，你应当能够：

1. 说清并查集的三个操作 MAKE-SET、UNION、FIND-SET 及分析参数 \(n\)（MAKE-SET 次数）和 \(m\)（总操作数）。
2. 用链表实现并查集，并用"小的并入大的"（加权合并）证明 \(O(m+n\lg n)\) 的界。
3. 写出按秩合并与路径压缩的森林实现（含非递归版本），说出它的 \(O(m\,\alpha(n))\) 界以及 \(\alpha(n)\le4\) 的实际含义。
4. 理解 21.4 节势函数分析的骨架：秩的性质、level 与 iter、FIND-SET 路径上"除至多 \(\alpha(n)+2\) 个结点外势能都下降"。
5. 用并查集实现相关性阈值分组，并说明它与单链接层次聚类、Kruskal 算法的等价关系及其"链式效应"。

读前导读

这一章在解决什么问题。 想象你在整理一张股票池：每发现"A 和 B 的相关性超过 0.5"，就把它们归到同一组；后来又发现"B 和 C 也超过 0.5"，那 A、B、C 就都是一组。随着这样的"关系记录"一条条进来，你需要随时回答两个问题：某只股票现在属于哪一组？两只股票是不是同一组？并查集（union-find）就是专门干这件事的数据结构，名字里的"并"是合并两组，"查"是查某个元素的组。

一个贴近 CPA 背景的类比：集团合并报表时要确定每家公司的最终控制人。每家子公司只登记"我的直接母公司是谁"，要找最终控制人就沿着"母公司的母公司"一路往上查，查到"没有母公司"的那家就是。两个集团合并，只需要让一个集团的顶层公司登记到另一个集团的顶层公司名下。本章的"森林"就是这种股权树，"根"就是最终控制人，FIND-SET 就是查最终控制人。两个提速技巧也都有对应：按秩合并 ≈ 让层级浅的集团并到层级深的集团下，避免股权链越来越长；路径压缩 ≈ 查过一次之后，把沿途每家子公司都直接登记到最终控制人名下，下次一步就查到。

先说清"图"是什么（第 22、23 章会大量用到）。 图就是点和线：点代表对象（股票、公司、账户），线代表两点之间的某种关系（相关性高、互相担保、持股）。没有方向的线叫"无向边"。如果从点 A 出发沿着线能走到点 B，就说 A、B 连通；互相连通的一群点叫一个连通分量——也就是本章说的"一组"。所以"按相关性阈值分组"就是"画出所有相关性超过阈值的线，然后找连通分量"。

需要先想起来的数学。

• 对数与"翻倍论证"。 从 1 开始不断翻倍，到 \(n\) 需要 \(\lg n\) 次（\(\lg=\log_2\)）。例如 \(n=1000\) 时 \(\lg n\approx10\)。本章最常用的论证就是"每被搬一次，所在组的大小至少翻倍，所以最多被搬 \(\lg n\) 次"。见 第 00 册第 04 章 级数与收敛。
• 函数迭代记号。 \(f^{(i)}(j)\) 表示把 \(f\) 连续作用 \(i\) 次，例如 \(f(j)=2j\) 时 \(f^{(3)}(1)=8\)。注意它不是"\(f\) 的 \(i\) 次方"。
• 反函数与 \(\min\{k:\cdots\}\)。 \(\min\{k: A_k(1)\ge n\}\) 读作"使 \(A_k(1)\ge n\) 成立的最小的 \(k\)"。见 第 00 册第 08 章 读懂数学证明与符号。
• 摊还分析与势函数。 21.4 节的分析用的是第 17 章的势能法；没读第 17 章也不影响使用并查集。

怎么读这一章。 21.1、21.2、21.3 是必读，其中 21.2 的"小的并入大的"论证短小而有用。21.4 原书标为选读，本章也只给骨架：第一次读只需要记住"\(\alpha(n)\) 实际上不超过 4，所以并查集几乎是线性时间"，跳过 21.4.2–21.4.4 的势函数细节完全不影响后面。21.5 可略读。21.6 量化实战值得细读，尤其是"链式效应"——它直接影响第 23 章用最小生成树做层次风险平价时的判断。

21.1 问题与操作

不相交集合数据结构（disjoint-set data structure）维护一族互不相交的动态集合 \(\mathcal S=\{S_1,\dots,S_k\}\)。每个集合用一个代表（representative）来标识，代表是集合中的某个成员。多数应用不在乎代表是谁，只要求集合没有变化时两次查询返回同一个代表。

每个元素用对象 \(x\) 表示，支持三个操作：

• MAKE-SET(x)：新建只含 \(x\) 的集合，\(x\) 就是代表。要求 \(x\) 不在其他集合中。
• UNION(x, y)：把含 \(x\) 的集合 \(S_x\) 和含 \(y\) 的集合 \(S_y\) 合并为并集。新代表可以是并集中任一成员。
• FIND-SET(x)：返回含 \(x\) 的集合的代表。

分析参数：\(n\) 为 MAKE-SET 的次数，\(m\) 为 MAKE-SET、UNION、FIND-SET 的总次数。每次 UNION 让集合数减 1，所以 UNION 至多 \(n-1\) 次；显然 \(m\ge n\)。约定前 \(n\) 个操作都是 MAKE-SET。

一个典型应用：无向图的连通分量

def CONNECTED_COMPONENTS(G):
    for v in G.V:
        MAKE_SET(v)
    for (u, v) in G.E:
        if FIND_SET(u) != FIND_SET(v):
            UNION(u, v)

def SAME_COMPONENT(u, v):
    return FIND_SET(u) == FIND_SET(v)

原书图 21.1：顶点 a–j，按边 (b,d)、(e,g)、(a,c)、(h,i)、(a,b)、(e,f)、(b,c) 的顺序处理，集合族逐步合并，最终得到四个连通分量 {a,b,c,d}、{e,f,g}、{h,i}、{j}。处理 (b,c) 时 b、c 已在同一集合，不再合并。

白话解释：代码里 G.V 是图的全部点（vertices），G.E 是全部线（edges），(u, v) 表示一条连接点 \(u\) 和点 \(v\) 的线。算法先让每个点自成一组，然后逐条看线：线两端若不在同一组，就把两组并起来。所有线看完，剩下的每一组就是一个连通分量。 用股票说：\(a\)–\(j\) 是 10 只股票，(b,d) 表示"b 和 d 相关性高"。读完 7 条关系后得到四组，其中 \(j\) 没有和任何股票高相关，独自一组。处理 (b,c) 时不必合并，是因为之前已经通过 (a,c)、(a,b) 把 b 和 c 间接连到了一起——这正是并查集能自动处理的"传递关系"。

如果图是静态的，用下一章的深度优先搜索求连通分量更快。并查集的优势在于边是逐条动态加入的：每加一条边只需一次 UNION，而不必重新搜索全图。按相关系数从高到低逐条加边、观察分组如何演化，正是这种场景。

21.2 链表表示

每个集合用一个链表表示（原书图 21.2）：集合对象有 head、tail 两个指针；链表中每个对象存一个成员、一个 next 指针，以及一个指回集合对象的指针。代表是链表中第一个成员。

• MAKE-SET：新建一个单元素链表，\(O(1)\)。
• FIND-SET：沿回指针找到集合对象，返回 head 所指成员，\(O(1)\)。
• UNION(x, y)：把 \(y\) 的链表接到 \(x\) 的链表尾部（用 tail 定位），然后把原 \(y\) 链表中每个对象的回指针都改指向 \(x\) 的集合对象。最后一步的代价与 \(y\) 链表的长度成正比。

最坏情况（图 21.3）：\(n\) 次 MAKE-SET 后依次执行 UNION(\(x_2,x_1\))、UNION(\(x_3,x_2\))、……、UNION(\(x_n,x_{n-1}\))，若每次都把长链接到短链上，第 \(i\) 次要改 \(i\) 个回指针，总计 \(\sum_{i=1}^{n-1}i=\Theta(n^2)\)，\(m=2n-1\) 个操作摊还每个 \(\Theta(n)\)。

加权合并启发式（weighted-union heuristic）：每个链表记录长度，总是把较短的链表接到较长的上。

定理 21.1　用链表和加权合并，\(m\) 个操作（其中 \(n\) 个 MAKE-SET）总时间 \(O(m+n\lg n)\)。

证明的核心论证非常值得记住：盯住某个对象 \(x\)。每当 \(x\) 的回指针被改写，\(x\) 都在较小的那个集合里，所以合并后 \(x\) 所在集合的大小至少翻倍。第一次改写后集合至少 2 个元素，第二次后至少 4 个……集合最多 \(n\) 个元素，因此 \(x\) 的回指针至多被改写 \(\lceil\lg n\rceil\) 次。\(n\) 个对象合计 \(O(n\lg n)\)，其余每个操作 \(O(1)\)，合计 \(O(m)\)。

推导拆解：取 \(n=8\)，跟踪某个元素 \(x\)。开始时 \(x\) 所在组大小为 1。第一次被搬（回指针被改写），说明它在较小的一方，合并后组大小 \(\ge1+1=2\)；第二次被搬，合并前它那组至少 2，对方至少同样大，合并后 \(\ge4\)；第三次后 \(\ge8\)。组大小不可能超过 8，所以第四次不会发生，\(x\) 至多被搬 \(3=\lg8\) 次。 关键在"较小的一方"这个条件：合并后大小 = 自己 + 对方 \(\ge\) 自己 + 自己 = 2 × 自己。没有加权规则时，同一个元素可能每次都在被搬的那一方，而对方只比它多一个元素，于是可以被搬 \(n-1\) 次，这就是 \(\Theta(n^2)\) 最坏情形的来源。

这种"小的并入大的"（small-to-large）论证在算法设计中反复出现：只要每次移动的都是较小的一方，每个元素被移动的次数就不超过 \(\lg n\)。

21.3 不相交集合森林

21.3.1 表示

更快的实现用有根树：每个集合是一棵树，每个结点只存一个父指针，根就是代表，根的父指针指向自己（原书图 21.4）。

• MAKE-SET：建一棵单结点树。
• FIND-SET：沿父指针一直走到根；经过的结点构成查找路径（find path）。
• UNION：让一棵树的根指向另一棵树的根。

朴素实现并不比链表快：\(n-1\) 次 UNION 可能造出一条 \(n\) 个结点的链，之后每次 FIND-SET 都是 \(\Theta(n)\)。

21.3.2 两个启发式

1. 按秩合并（union by rank）：每个结点维护一个秩（rank），它是结点高度的上界。UNION 时让秩小的根指向秩大的根；两根秩相等时任选一个作父亲，并把它的秩加 1。
2. 路径压缩（path compression）：FIND-SET 时，让查找路径上每个结点都直接指向根（原书图 21.5）。路径压缩不改变任何结点的秩。

金融直觉：用股权结构来理解。每个结点是一家公司，父指针是"直接母公司"，根是最终控制人。 查最终控制人（FIND-SET）要沿股权链一级级往上走，链越长越慢。按秩合并：两个集团合并时，让股权层级较浅的集团整体挂到较深的集团顶层公司下面，这样合并后的最长链不会变长（除非两边一样深，才加一层，这就是"秩相等时加 1"）。路径压缩：某次查询走了 5 级才查到最终控制人，那就顺手把沿途 5 家公司都改登记为"直接由最终控制人持有"，以后再查就是一步。 "秩"是高度的上界而不是高度本身：路径压缩把树压扁后，真实高度可能变小，但秩不跟着改，这样分析起来更简单，也不影响正确性。

def MAKE_SET(x):
    x.p = x
    x.rank = 0

def UNION(x, y):
    LINK(FIND_SET(x), FIND_SET(y))

def LINK(x, y):              # x, y 都是根
    if x.rank > y.rank:
        y.p = x
    else:
        x.p = y
        if x.rank == y.rank:
            y.rank += 1

def FIND_SET(x):             # 两趟法：递归上行找根，返回时逐个指向根
    if x != x.p:
        x.p = FIND_SET(x.p)
    return x.p

FIND-SET 是两趟方法（two-pass method）：递归调用一路向上找到根，递归返回时一路向下把每个结点的父指针改成根。工程上递归深度可能很大（在 Python 里会触发递归上限），通常改写成两个 while 循环（原书 21.3-2，本章 21.6 节的代码就是这样写的）。

21.3.3 效果

\(\alpha(n)\) 增长得极其缓慢，在任何可以想象的应用中都不超过 4，所以实践上可以把并查集看作线性时间。每个元素只需 \(O(1)\) 空间（父指针 + 秩），秩本身只需 \(O(\lg\lg n)\) 位（原书 21.4-3）。

21.4 为什么是 \(\alpha(n)\)：分析的骨架

原书 21.4 节是选读节，证明相当精巧。这里给出骨架，需要细节时回原书 p.594–603。

21.4.1 一个增长极快的函数和它的反函数

对整数 \(k\ge0\)、\(j\ge1\) 定义

其中 \(A^{(i)}\) 表示函数迭代 \(i\) 次（\(A^{(0)}(j)=j\)）。\(k\) 称为级（level）。容易归纳得到 \(A_1(j)=2j+1\)，\(A_2(j)=2^{j+1}(j+1)-1\)。具体数值：

最后这个数远远超过可观测宇宙的原子数（约 \(10^{80}\)）。

推导拆解：定义的意思是：第 \(k\) 级函数 = 把第 \(k-1\) 级函数连续作用 \(j+1\) 次。 \(k=0\)：\(A_0(j)=j+1\)，就是"加 1"。 \(k=1\)：把"加 1"做 \(j+1\) 次，\(A_1(j)=j+(j+1)=2j+1\)，大约是"翻倍"。 \(k=2\)：把"大约翻倍"做 \(j+1\) 次，于是大约乘了 \(2^{j+1}\)，精确结果是 \(2^{j+1}(j+1)-1\)。检验 \(j=1\)：\(A_2(1)=A_1(A_1(1))=A_1(3)=7\)，公式给出 \(4\times2-1=7\)。 \(k=3\)：把"指数级增长"再迭代 \(j+1\) 次，已经是"指数塔"。\(A_3(1)=A_2(A_2(1))=A_2(7)=2^8\times8-1=2047\)。 每升一级，增长速度就从"加法"到"乘法"到"指数"到"指数塔"再往上跳一档，所以 \(A_4(1)\) 大得无法想象。

定义反函数

于是 \(\alpha(n)=0\)（\(n\le2\)）、\(1\)（\(n=3\)）、\(2\)（\(4\le n\le7\)）、\(3\)（\(8\le n\le2047\)）、\(4\)（\(2048\le n\le A_4(1)\)）。只有 \(n\) 超过 \(A_4(1)\) 才有 \(\alpha(n)>4\)。

白话解释：\(\alpha(n)\) 问的是"\(n\) 要爬到第几级函数才够得着"。因为 \(A_k(1)\) 长得极快，\(\alpha(n)\) 就长得极慢：全 A 股约 5000 只股票，\(\alpha=4\)；全球所有证券、所有逐笔成交记录加起来，仍然是 4。所以 \(O(m\,\alpha(n))\) 在实际中可以当作 \(O(4m)\)，即"每次操作平均常数步"。这里 \(\alpha\) 与资产定价里的 alpha 毫无关系，只是同一个希腊字母。

21.4.2 秩的性质

• 引理 21.4：对所有结点 \(x\)，\(x.rank\le x.p.rank\)，若 \(x\) 不是根则严格小于。\(x.rank\) 从 0 开始增长，直到 \(x\) 不再是根后就不再变化；\(x.p.rank\) 随时间单调不减。
• 推论 21.5：从任一结点到根的路径上，秩严格递增。
• 引理 21.6：每个结点的秩至多 \(n-1\)（实际上至多 \(\lfloor\lg n\rfloor\)，原书 21.4-2，但弱界已够用）。

分析时把每个 UNION 看作两次 FIND-SET 加一次 LINK，操作数至多变成原来的 3 倍，不影响渐近界（引理 21.7）。

21.4.3 势函数

对每个结点 \(x\) 定义势 \(\phi_q(x)\)（\(q\) 为已执行的操作数），总势 \(\Phi_q=\sum_x\phi_q(x)\)。

• 若 \(x\) 是根或 \(x.rank=0\)：\(\phi_q(x)=\alpha(n)\cdot x.rank\)。

• 否则先定义两个辅助量：

  • \(\mathrm{level}(x)=\max\{k: x.p.rank\ge A_k(x.rank)\}\)，即父亲的秩比自己"高出几个级别"，满足 \(0\le\mathrm{level}(x)<\alpha(n)\)；
  • \(\mathrm{iter}(x)=\max\{i: x.p.rank\ge A^{(i)}_{\mathrm{level}(x)}(x.rank)\}\)，即在这个级别上能迭代几次，满足 \(1\le\mathrm{iter}(x)\le x.rank\)；

  然后令 \(\phi_q(x)=(\alpha(n)-\mathrm{level}(x))\cdot x.rank-\mathrm{iter}(x)\)。

由这些范围可得 \(0\le\phi_q(x)\le\alpha(n)\cdot x.rank\)（引理 21.8）。直观上，父亲的秩越比自己高，结点的势就越低；路径压缩让结点的父亲变成秩更高的根，于是势下降，下降的势正好支付压缩的工作。

白话解释：level 和 iter 合起来是一把两级刻度的尺子，用来量"父亲的秩比我高出多少"。level 是粗刻度：父亲的秩够得着第几级函数 \(A_k\) 作用在我的秩上。iter 是细刻度：在这一级上，还能再多作用几次。每次路径压缩让父亲换成更高的祖先，读数就只增不减；读数越高，势越低。因为 level 最多只有 \(\alpha(n)\) 档、每档内 iter 至多 \(x.rank\) 格，一个结点的势最多能降 \(\alpha(n)\cdot x.rank\) 次——这就把总工作量限住了。

21.4.4 三个操作的摊还代价

• MAKE-SET：新结点秩 0、势 0，摊还 \(O(1)\)。
• LINK：实际 \(O(1)\)。只有两根及原来那个根的孩子的势可能变化；孩子的势不增，被挂下去的根的势不增，仍为根的那个秩至多加 1，势至多增 \(\alpha(n)\)。摊还 \(O(\alpha(n))\)。
• FIND-SET：设路径上有 \(s\) 个结点，实际 \(O(s)\)。关键论断（引理 21.13）：除了至多 \(\alpha(n)+2\) 个结点外，路径上每个结点的势都至少下降 1。例外的结点是：路径起点（若秩为 0）、根，以及每个级别 \(k=0,\dots,\alpha(n)-1\) 上 level 为 \(k\) 的最后一个结点。对其余结点 \(x\)，路径上更靠后存在一个与它 level 相同的结点 \(y\)，于是

压缩后 \(x\) 的父亲变成根，秩至少是 \(y.p.rank\)，所以 iter 至少加 1 或者 level 上升，势至少降 1。摊还代价为 \(O(s)-(s-\alpha(n)-2)=O(\alpha(n))\)。

推导拆解：设 \(k=\mathrm{level}(x)=\mathrm{level}(y)\)，\(i=\mathrm{iter}(x)\)。不等式链每一步的依据： 第一个 \(\ge\)：\(y\) 的 level 是 \(k\)，按 level 的定义，\(y.p.rank\ge A_k(y.rank)\)。 第二个 \(\ge\)：\(y\) 在路径上位于 \(x\) 的父亲或更靠上，路径上秩严格递增（推论 21.5），所以 \(y.rank\ge x.p.rank\)；\(A_k\) 是递增函数，自变量变大函数值不减。 第三个 \(\ge\)：iter 的定义给出 \(x.p.rank\ge A_k^{(i)}(x.rank)\)，再用一次 \(A_k\) 递增。 最后的 \(=\)：多作用一次 \(A_k\)，迭代次数从 \(i\) 变成 \(i+1\)。 结论：压缩后 \(x\) 的新父亲（根）的秩 \(\ge A_k^{(i+1)}(x.rank)\)，所以细刻度 iter 至少加 1；若加到超出上限，就进位到更高的 level。两种情况势都至少降 1。最后一句的代数：实际工作 \(s\) 步，其中至少 \(s-\alpha(n)-2\) 个结点各降 1 单位势，相抵后只剩 \(O(\alpha(n))\)。

定理 21.14　采用按秩合并与路径压缩的不相交集合森林上，\(m\) 个操作（其中 \(n\) 个 MAKE-SET）的最坏时间为 \(O(m\,\alpha(n))\)。

原书注记还提到：Tarjan 证明了满足一定条件的任何并查集结构都需要 \(\Omega(m\hat\alpha(m,n))\) 时间，所以这个界本质上是最优的；路径压缩还有常数因子更好的"一趟法"变体，如路径分裂（path splitting）和路径减半（path halving）。

21.5 思考题选讲

• 21-1 离线最小值：对 \(\{1,\dots,n\}\) 执行一串 INSERT 和 EXTRACT-MIN，事先知道整个序列，求每次 EXTRACT-MIN 的返回值。原书实例 4, 8, E, 3, E, 9, 2, 6, E, E, E, 1, 7, E, 5 的答案依次是 4, 3, 2, 6, 8, 1。做法：按关键字从小到大，看它被插入在第几段 \(K_j\)，它就是第 \(j\) 次 EXTRACT-MIN 的结果，然后把 \(K_j\) 并入下一个仍存在的段。用并查集实现近乎线性。
• 21-2 深度确定：维护有根树森林，支持把一棵树的根接到另一棵树的某个结点下，并查询结点深度。用并查集，每个结点存一个"伪距离"，使到集合根路径上伪距离之和等于真实深度；路径压缩时顺便累加。这就是常说的"带权并查集"，可以用来维护"相对于组代表的偏移量"，例如同一主体不同证券之间的换股比例。
• 21-3 Tarjan 离线最近公共祖先：对有根树做 DFS，访问完一个孩子就把它的集合并入父亲，集合的 ancestor 字段记当前结点；处理查询对 \(\{u,v\}\) 时若 \(v\) 已访问完，答案就是 FIND-SET(v).ancestor。总时间近乎线性。

21.6 量化实战：用并查集做分组

21.6.1 三类典型用途

相关性阈值分组。 把相关系数超过阈值 \(\theta\) 的股票对连一条边，连通分量就是"高度相关组"。这可以用来构造统计意义上的行业（不依赖官方行业分类）、对高度相关的因子去冗余、为配对交易筛选候选池。实现上就是对所有 \(\rho_{ij}>\theta\) 的对执行 UNION。

这种分组与单链接层次聚类（single-linkage clustering）在距离 \(1-\theta\) 处的切割完全相同：单链接把两组之间最近的那对的距离定义为组间距离，"存在一条相关性超过阈值的链"就够把两组连起来。如果把边按相关系数从高到低依次加入，记录每次真正发生合并时的阈值，得到的就是完整的单链接聚类树——这和第 23 章的 Kruskal 最小生成树是同一个过程。

链式效应（chaining）是这种分组的主要弱点：只要两组之间有一对股票相关性偶然偏高，两组就整体合并。股票数为 \(N\) 时有 \(N(N-1)/2\) 对，估计噪声下总会有一些组间相关性被高估，所以阈值一放低，所有股票会突然连成一大团。下面的实验会清楚地看到这一点。

实体解析（entity resolution）。同一家公司可能有多个标识：更名前后的简称、A 股和 H 股代码、债券发行主体名称、数据供应商的内部 ID。每条"两个标识指向同一主体"的映射记录就是一次 UNION，最后每个连通分量就是一个主体。处理历史数据时把公司更名、代码变更、合并重组归到一起，是构建无幸存者偏差股票池的前置步骤。

动态连通性。例如逐日加入新的持股关系、担保关系或供应链关系，实时查询两家公司是否处于同一个关联网络中。

21.6.2 代码

代码分三部分：(1) 故意构造长链，对比朴素实现和"按秩合并 + 路径压缩"沿父指针走的总步数；(2) 模拟 8 个行业、120 只股票的单因子加行业因子收益，在不同阈值下用并查集分组，用调整兰德指数（ARI，1 表示与真实行业完全一致）评价，并验证与 scipy 单链接切割结果一致；(3) 一个虚构的证券标识实体解析例子。

import numpy as np
from scipy.cluster.hierarchy import linkage, fcluster
from scipy.spatial.distance import squareform
from sklearn.metrics import adjusted_rand_score

class UnionFind:
    """不相交集合森林：按秩合并 + 路径压缩（非递归两趟法）。"""
    def __init__(self, n):
        self.p = list(range(n)); self.rank = [0]*n; self.size = [1]*n
        self.steps = 0                                   # 统计沿父指针走的步数
    def find(self, x):
        root = x
        while self.p[root] != root:                      # 第一趟：找根
            root = self.p[root]; self.steps += 1
        while self.p[x] != root:                         # 第二趟：路径上全部指向根
            self.p[x], x = root, self.p[x]
        return root
    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.p[ry] = rx; self.size[rx] += self.size[ry]   # 秩小的根挂到秩大的根下
        if self.rank[rx] == self.rank[ry]: self.rank[rx] += 1
        return True

class NaiveUF(UnionFind):
    def find(self, x):
        while self.p[x] != x: x = self.p[x]; self.steps += 1
        return x
    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx != ry: self.p[ry] = rx; return True
        return False

# ---------- 1. 两种启发式的效果：故意造一条长链再反复查询 ----------
n = 20000
for cls in (NaiveUF, UnionFind):
    uf = cls(n)
    for i in range(1, n): uf.union(i, i-1)              # 朴素实现会形成线性链
    rng = np.random.default_rng(0)
    for x in rng.integers(0, n, 20000): uf.find(int(x))
    print(f"{cls.__name__:10s} 2 万次 UNION + 2 万次 FIND 共走父指针 {uf.steps:>12,d} 步")

# ---------- 2. 相关性阈值分组：模拟 8 个行业、120 只股票 ----------
rng = np.random.default_rng(21)
n_ind, per, T = 8, 15, 500
labels = np.repeat(np.arange(n_ind), per)
mkt = rng.normal(0, 0.010, T)
ind = rng.normal(0, 0.008, (T, n_ind))
beta_ind = rng.uniform(0.6, 1.4, n_ind*per)
R = mkt[:, None] + ind[:, labels]*beta_ind + rng.normal(0, 0.012, (T, n_ind*per))
C = np.corrcoef(R.T)
N = C.shape[0]
iu = np.triu_indices(N, 1)

for th in [0.55, 0.50, 0.45, 0.40, 0.35]:
    uf = UnionFind(N)
    for i, j in zip(*iu):
        if C[i, j] > th: uf.union(i, j)
    grp = np.array([uf.find(i) for i in range(N)])
    sizes = sorted(np.bincount(np.unique(grp, return_inverse=True)[1]).tolist(), reverse=True)
    print(f"阈值 ρ>{th:.2f}: 组数={len(sizes):3d}, 最大 5 组规模={sizes[:5]}, "
          f"与真实行业 ARI={adjusted_rand_score(labels, grp):.3f}")

# 与单链接层次聚类在同一高度切割的结果完全相同
th = 0.35
D = 1 - C; np.fill_diagonal(D, 0)
Z = linkage(squareform(D, checks=False), method="single")
lab_sl = fcluster(Z, t=1 - th, criterion="distance")   # 距离 < 1-th 的合在一起
uf = UnionFind(N)
for i, j in zip(*iu):
    if C[i, j] > th: uf.union(i, j)
grp = np.array([uf.find(i) for i in range(N)])
print("并查集阈值分组 与 单链接切割 是否一致:", adjusted_rand_score(lab_sl, grp) == 1.0)

# ---------- 3. 证券标识的实体解析：代码变更、更名、跨市场映射 ----------
events = [("600AAA.SH", "甲公司"), ("甲公司", "甲控股"),          # 更名：甲公司 -> 甲控股
          ("000BBB.SZ", "乙股份"), ("乙股份", "0BBB.HK"),        # A+H 两地上市
          ("0BBB.HK", "乙集团"), ("601CCC.SH", "丙能源"),
          ("0CCC.HK", "丙能源股份"), ("丙能源股份", "丙能源"),
          ("600DDD.SH", "丁科技")]                                # 没有关联的独立主体
ids = sorted({x for e in events for x in e}); idx = {s: i for i, s in enumerate(ids)}
uf = UnionFind(len(ids))
for a, b in events: uf.union(idx[a], idx[b])
groups = {}
for s in ids: groups.setdefault(uf.find(idx[s]), []).append(s)
for g in groups.values(): print("同一主体:", g)

运行输出：

NaiveUF    2 万次 UNION + 2 万次 FIND 共走父指针  200,278,665 步
UnionFind  2 万次 UNION + 2 万次 FIND 共走父指针       39,997 步
阈值 ρ>0.55: 组数= 62, 最大 5 组规模=[12, 11, 10, 10, 8], 与真实行业 ARI=0.455
阈值 ρ>0.50: 组数= 21, 最大 5 组规模=[15, 15, 14, 14, 13], 与真实行业 ARI=0.873
阈值 ρ>0.45: 组数=  8, 最大 5 组规模=[30, 15, 15, 15, 15], 与真实行业 ARI=0.855
阈值 ρ>0.40: 组数=  1, 最大 5 组规模=[120], 与真实行业 ARI=0.000
阈值 ρ>0.35: 组数=  1, 最大 5 组规模=[120], 与真实行业 ARI=0.000
并查集阈值分组 与 单链接切割 是否一致: True
同一主体: ['000BBB.SZ', '0BBB.HK', '乙股份', '乙集团']
同一主体: ['0CCC.HK', '601CCC.SH', '丙能源', '丙能源股份']
同一主体: ['600AAA.SH', '甲公司', '甲控股']
同一主体: ['600DDD.SH', '丁科技']

解读：

• 启发式的威力：同样 2 万次合并加 2 万次查询，朴素实现走了约 2 亿步（链被反复从头走到尾），按秩合并加路径压缩只走了约 4 万步，平均每次操作约 1 步。
• 阈值的敏感性：在这个模型里，同行业股票的理论相关性约 0.53，跨行业约 0.32。阈值 0.50 时 ARI 最高（0.873），行业大致成形，但一些股票还没连上；阈值 0.45 时组数恰好是 8，但其中一组有 30 只——两个行业因为少数几对偶然偏高的相关性被整体并在一起；阈值降到 0.40，仍高于跨行业的理论相关性 0.32，所有股票却已经连成一团。这就是链式效应：\(120\times119/2=7140\) 对相关系数里，估计误差（\(T=500\) 时标准误约 0.04）总会让几十对跨行业相关性超过 0.40，而只要一对就够了。

推导拆解：标准误 0.04 从哪里来？样本相关系数的近似标准误为 \((1-\rho^2)/\sqrt{T}\)。跨行业 \(\rho\approx0.32\)、\(T=500\) 时约为 \((1-0.10)/22.4\approx0.040\)。要从 0.32 被高估到 0.40 以上，需要偏离约 2 个标准误，单侧概率约 2.3%。跨行业的股票对大约有 \(7140\times\tfrac78\approx6250\) 对，期望约有 \(6250\times2.3\%\approx140\) 对越过阈值。这只是粗略估算（各对相关系数的误差并不独立），但足以说明"总会有几十上百对"。 金融直觉：这和多重检验是同一个问题：单看一对，偶然越线的概率很小；同时看几千对，几乎必然有一些越线。单链接分组对这种偶然"只要一对就合并"，所以特别脆弱。

• 等价性：并查集阈值分组和 scipy 单链接聚类在同一高度切割的结果完全一致。实践中，若要稳健的分组，通常会改用平均链接、Ward 法，或者在聚类前先对相关矩阵去噪（例如去掉市场因子、用随机矩阵理论截断特征值）；但单链接（也就是 MST）仍是第 23 章层次风险平价的默认第一步，所以必须清楚它的这个弱点。
• 实体解析：映射记录不需要按任何顺序给出，并查集自动把传递关系（甲公司—甲控股—600AAA.SH）合到一起。实际工作中，还要配合时间区间（某个代码在哪段时间属于哪个主体），只用并查集是不够的，但它是第一步。

本章小结

并查集维护一族不相交集合，支持 MAKE-SET、UNION、FIND-SET。链表实现中 FIND-SET 是 \(O(1)\)，UNION 需要改写回指针，加权合并（小的并入大的）使每个元素至多被搬 \(\lg n\) 次，总时间 \(O(m+n\lg n)\)。森林实现配合按秩合并与路径压缩，总时间 \(O(m\,\alpha(n))\)，其中 \(\alpha(n)\) 是阿克曼型函数 \(A_k(1)\) 的反函数，实际中不超过 4。分析靠一个以 level 和 iter 刻画"父亲比自己高多少"的势函数：路径压缩让结点的父亲变高、势能下降，从而支付压缩的工作。在量化中，并查集用于相关性阈值分组（等价于单链接聚类，有链式效应）、证券标识的实体解析和动态关联网络的连通性查询，也是 Kruskal 最小生成树的核心部件。

练习

基础

1. 设无向图有 \(k\) 个连通分量，CONNECTED-COMPONENTS 中 FIND-SET 被调用多少次？UNION 被调用多少次？（原书 21.1-3。提示：\(2|E|\) 次和 \(|V|-k\) 次。）
2. 写出带加权合并的链表版 MAKE-SET、FIND-SET、UNION 伪代码，并把定理 21.1 的聚合证明改写为摊还界：MAKE-SET、FIND-SET \(O(1)\)，UNION \(O(\lg n)\)。（原书 21.2-1、21.2-3。）
3. 写出非递归、带路径压缩的 FIND-SET。（原书 21.3-2。）
4. 构造一个只用按秩合并（不用路径压缩）时需要 \(\Omega(m\lg n)\) 时间的操作序列。（原书 21.3-3。提示：先用 UNION 造出秩为 \(\lg n\) 的二项树形状，再反复查询最深的结点。）
5. 证明只用按秩合并时每个结点的秩不超过 \(\lfloor\lg n\rfloor\)。（原书 21.4-2。提示：归纳证明秩为 \(r\) 的根所在树至少有 \(2^r\) 个结点。）

进阶

6. 证明若所有 LINK 都出现在所有 FIND-SET 之前，按秩合并加路径压缩的总时间是 \(O(m)\)。（原书 21.3-5。）
7. Dante 教授认为查找路径上结点的 level 单调递增，这是否正确？（原书 21.4-5。提示：不正确。）
8. 修改 21.6.2 的代码：把所有股票对按相关系数从高到低排序，逐对 UNION，每次真正合并时记录"当前相关系数"和"当前组数"，画出组数随阈值变化的曲线。把这个序列和 scipy.cluster.hierarchy.linkage(method="single") 返回的合并高度对照，验证它们完全相同。
9. 实现思考题 21-2 的"带权并查集"：每个结点存 \(v.d\) 表示到父结点的偏移，路径压缩时累加偏移。用它维护一组证券之间的换算比例（例如 A 股与 H 股的股数换算、拆股前后的复权因子），查询任意两个标识之间的比例。
10. 在 21.6.2 的模拟中，先从每只股票的收益中回归掉市场因子（或者从相关矩阵中去掉最大特征值对应的成分），再做阈值分组。链式效应是否减轻？为什么？

原书推荐习题：21.1-3、21.2-3、21.3-2、21.3-3、21.4-2、21.4-4，思考题 21-1、21-3。

原书对照