文档教程示例工程【免费下载链接】CLRS:notebook:Solutions to Introduction to Algorithms项目地址https://gitcode.com/gh_mirrors/cl/CLRS点击查看免费下载本文以《算法导论》CLRS第 21 章“Data Structures for Disjoint Sets”章末问题Problem 21-1Off-line minimum为核心完整讲解离线最小值问题的定义、同质子序列划分、OFF-LINE-MINIMUM算法伪代码、正确性证明以及如何用不相交集合并查集Union-Find数据结构将实现复杂度压缩到近线性的O(nα(n))。文中给出的实例推演、算法步骤与复杂度结论全部取自仓库文档 C21-Data-Structures-for-Disjoint-Sets/problem.md并结合作者整理的工程实现 uf.cpp 进行源码级验证。读完本文你将掌握“离线”场景下批量预测EXTRACT-MIN返回值的思想并能独立把这类问题映射到并查集上的MAKE-SET / FIND-SET / UNION操作。问题定义在“离线”前提下预测每次 EXTRACT-MIN 的返回值离线最小值问题off-line minimum problem要求维护一个动态集合 T元素来自定义域{1, 2, ..., n}其上仅支持两种操作INSERT向集合 T 中插入一个新键EXTRACT-MIN返回并删除 T 中的当前最小值。我们拿到一个操作序列 S其中包含n 次 INSERT和m 次 EXTRACT-MIN并且定义域{1, 2, ..., n}中的每个键恰好被插入一次。任务是为每次EXTRACT-MIN调用确定它返回的键即填充数组extracted[1..m]对i 1, 2, ..., mextracted[i]是第 i 次EXTRACT-MIN返回的键。所谓“离线”off-line是指我们被允许在处理整个序列 S 之后才逐个确定所有返回值——这与在线online场景相反在线场景要求在每次EXTRACT-MIN执行时就立即返回答案。离线的自由度给了我们优化空间可以一次性观察全部 INSERT 的落点再用合适的数据结构批量求解。手工推演一个 14 步实例的 extracted 数组问题 a文档给出了如下实例其中数字代表一次INSERT字母E代表一次EXTRACT-MIN4, 8, E, 3, E, 9, 2, 6, E, E, E, 1, 7, E, 5这里的 n 10键 1..10m 6共 6 次 E。EXTRACT-MIN的行为可以理解为每个 E 返回它之前出现、且尚未被返回过的最小值。逐次推演如下步骤已插入且未被取出的键本次 E 的返回值第 1 个 E{4, 8}4第 2 个 E{3, 8}3第 3 个 E{9, 2, 6, 8}2第 4 个 E{6, 8, 9}6第 5 个 E{8, 9}8第 6 个 E{1, 7, 9}1因此得到的答案数组为extracted [4, 3, 2, 6, 8, 1]注意键 5、7、9 在最后一次EXTRACT-MIN之后才插入或始终未被取出它们不会被写入extracted——这正对应下文算法中j m1的“不写入”分支。把序列切成同质子序列与集合 K_j为了把“离线”优势显式化文档将序列 S 表示为如下同质子序列homogeneous subsequences形式I1, E, I2, E, I3, ..., Im, E, Im1其中每个E代表一次EXTRACT-MIN调用而每个I_j代表一段可能为空的连续INSERT序列。对每个子序列I_j把其中插入的键放入一个集合K_j若I_j为空则K_j为空集。这样划分的关键观察是第 j 次EXTRACT-MIN只能从K_1 ∪ ... ∪ K_j中取值因为I_{j1}之后的键还没有被插入键i在算法中只关心它落在哪个 K_j 里——这天然地对应并查集“元素属于哪个集合”的语义。OFF-LINE-MINIMUM 算法伪代码与执行语义基于上述划分文档给出的核心算法如下OFF-LINE-MINIMUM(m, n) for i - 1 to n do determine j such that i ∈ K[j] if j ! m 1 extracted[j] i let l be the smallest value greater than j for which set K[l] exists K[l] K[j] ∪ K[l], destroying K[j] return extracted逐行语义解读determine j such that i ∈ K[j]按键从小到大i 1..n处理。每个键恰好属于一个K_j这一步回答“键 i 是在哪一段 INSERT 中进来的”。if j ! m 1若j m1说明键 i 是在最后一次EXTRACT-MIN之后才插入的永远不会被任何一次提取返回因此不写入extracted。extracted[j] i否则键 i 就是第 j 次提取的返回值。由于按从小到大处理键当处理到 i 时所有比 i 小的键都已正确分配完毕因此第 j 次提取“当前最小”必然轮到 i。合并取j之后第一个仍然存在的集合K_l最小的l j把K_j并入K_l并销毁K_j。这相当于“撤销”第 j 次提取K_j中剩余的键原本只能被第 j 次提取返回现在 j 已被分配这些键就只能顺延给后续的提取因此并入其后第一个“还活着”的集合是语义上最精确的转移。正确性证明问题 b文档给出的证明分为两步先证每个被写入的值都正确再证数组被完整填满。第一步写入的值正确。用归纳法。假设前i-1个整数即1, ..., i-1都已正确写入extracted现在处理整数 i。算法确定j使得i ∈ K_j——该 j 必然存在因为在任意截断点上 INSERT 的次数总是不少于 EXTRACT-MIN 的次数每次提取都必须有键可返回。若j m1则 i 在全部提取之后才插入不写入数组是正确行为。若j ≤ m则第 j 次提取恰好发生在I_j之后它必须返回 i因为所有比 i 小的键都已被正确分配给了更早的提取而 i 在I_j中才被插入不可能被第 j 次之前的任何提取返回。处理完 i 之后算法“消除”第 j 次提取将I_j与I_ll j且K_l尚未被合并过的最小者中的键合并。这给出一个语义等价的新序列被移除的提取已经把正确返回值1..i记录在案剩余待提取的键仍在剩余子序列中合并意味着I_j中的剩余键只能在尚未被移除的第 j 次之后的提取中被返回——这恰好解释了为什么要找“最小的、尚未合并的l j”。新序列与原序列产生相同的提取结果故算法输出的每次提取都正确。第二步数组完整填满。反证法。假设某一步存在最小的未被填充位置 j设其正确值为 i。由于 j 之前的每次提取都被正确填充其中必然不含 i。当算法处理整数 i 时集合K_j尚未被移除否则extracted[j]已被填充。键 i 位于 j 之前的某个插入子序列中因此当前它一定在K_1, ..., K_j的某一个集合里。若它在某个K_kk ≠ j中则算法会把extracted[k]填成 i这与“j 之前的所有位置均已正确填满”矛盾。因此i ∈ K_j算法把extracted[j]正确填成 i归纳完成数组必然被完整且正确地填满。用不相交集合实现高效 OFF-LINE-MINIMUM问题 c朴素实现中“determine j such that i ∈ K[j]”需要维护 n 个集合并在合并时重排代价很高。文档给出的方案是引入并查集不相交集合数据结构并为其集合代表representative额外维护三段元信息整数j该集合对应的编号即K_j的编号整数prev与next分别指向前一个、后一个尚未被合并的集合从而把所有存活的K_j组织成一条双向链表。初始化方式显然集合按K_0, K_1, ..., K_{m1}建立K_0的prev置为-1K_{m1}的next置为-1表示不存在。三种核心操作与伪代码的对应关系如下伪代码操作并查集实现说明determine j such that i ∈ K[j]一次FIND(i)随后读取代表节点上存储的编号 jFIND 定位 i 所在集合的代表编号字段即 jlet l be the smallest value j for which K[l] exists读取代表节点的next指针链表只保留未合并集合next就是最小的存活后继由于此时j ≠ m1next必然存在K[l] K[j] ∪ K[l], destroying K[j]一次UNION同时维护双向链表把被删除集合从链表中摘除再做传统的集合合并链表摘除的具体步骤对应文档第 6 行取出K_j代表的prev若存在把该前驱集合的next指向K_j代表的next前驱集合的“下一个”变成当前集合的“下一个”对称地取出K_j代表的next若存在把该后继集合的prev指向K_j代表的prev最后执行一次传统的UNION(K_j, K_l)——按并查集定义合并两个集合即可合并后新集合继承代表节点上的j / prev / next字段链表结构不受破坏。复杂度账目整个循环共执行恰好 n 次FIND每个键一次与恰好 m 次UNION每个K_j在算法运行中被删除且只删除一次。再加上初始化阶段的 n 次MAKE-SET在同时使用**按秩合并union by rank与路径压缩path compression**的前提下单次操作的摊还代价为O(α(n))于是总复杂度为O(n (nm)·α(n)) O(n·α(n))其中α(n)是增长极其缓慢的阿克曼反函数对任何实际规模的输入都可视为常数因此该实现在实践中是近线性的。复杂度背景为什么必须“按秩合并 路径压缩”并用O(nα(n))的结论依赖两种启发式同时生效。仓库文档 21.3.md 的习题 21.3-3 指出如果只用按秩合并、不做路径压缩可以构造一个含 n 次MAKE-SET、总共 m 次操作的操作序列其代价下界为Ω(m lg n)——即退化为对数级。该下界的构造如下见下图先执行 n 次MAKE-SET再执行2^⌊log₂n⌋ - 1次UNION按规则构建出一棵度为⌊log₂n⌋的二项树文中给出了度为 2 时的构建示例树的最深层节点值为 k最后连续执行m - n - 2^⌊log₂n⌋ 1次FIND-SET(k)每次查询沿最深层到根的路径走Θ(⌊log₂n⌋)步从而把整个序列的总时间下界推高到Ω(m lg n)。这解释了问题 c 的实现为何必须同时保留路径压缩只有按秩合并时树深可达Θ(lg n)而一旦叠加路径压缩摊还代价即从O(lg n)降到O(α(n))才支撑起OFF-LINE-MINIMUM的O(nα(n))总复杂度。仓库配套源码uf.cpp 中的工程化 Union-Find仓库为第 21 章提供了可直接编译运行的并查集实现 C21-Data-Structures-for-Disjoint-Sets/uf.cpp它在文档习题 21.3-2“写出带路径压缩的非递归 FIND-SET”中被引用为参考实现。核心类UF的关键设计如下class UF { private: vectorint parent; vectorint rank; int count; int N; int find(int p) { if (!validate(p)) return -1; while (p ! parent[p]) { parent[p] parent[parent[p]]; // path compression by halving p parent[p]; } return p; } void Union(int p, int q) { int rootP find(p); int rootQ find(q); if (rootP rootQ) return; // make root of smaller rank point to root of larger rank if (rank[rootP] rank[rootQ]) parent[rootP] rootQ; else if (rank[rootP] rank[rootQ]) parent[rootQ] rootP; else { parent[rootQ] rootP; rank[rootP]; } count--; } };对应到问题 c 的实现要点find采用路径折半压缩path compression by halving把沿途节点直接指向其祖父节点仅用迭代、无递归正是习题 21.3-2 要求的非递归版本Union采用按秩合并小秩树的根指向大秩树的根秩相等时深度加一count字段跟踪当前连通分量个数getCount()与connected(p, q)提供了与第 21.1 节CONNECTED-COMPONENTS算法一致的查询接口。若要在问题 c 的场景中落地该实现只需让UF的每个集合代表额外携带文档要求的j / prev / next三个字段即可把OFF-LINE-MINIMUM的第 2、4、6 行分别映射为find、next字段读取与Union并将count语义替换为“尚未被删除的K_j集合数”。仓库中 21.1.md 与 21.2.md 还分别用连通分量问题每次迭代调用FIND-SET共2|E|次、UNION共|V|-k次和链表表示 加权合并启发式从不同实现路线印证了并查集接口与复杂度分析的一致性。小结离线最小值问题展示了一个典型模式把“在线”必须即时回答的问题延后到“离线”批量处理从而用更强的数据结构换取更优的复杂度。其求解路径清晰可复现把操作序列切分为I1, E, I2, E, ..., Im, E, Im1并建立集合K_j按键从小到大执行OFF-LINE-MINIMUM每个键至多触发一次FIND和一次UNION用“代表节点携带 j/prev/next”的并查集实现使整体复杂度达到O(nα(n))。整套推导含实例答案[4,3,2,6,8,1]、正确性归纳证明与复杂度结论均可在仓库文档 C21-Data-Structures-for-Disjoint-Sets/problem.md 中核对工程实现可参考 uf.cpp。理解这一题之后处理“批量提取最小值”“离线批量查询”一类问题如按时间线预测队头出队元素时就能直接套用这套并查集 集合合并的建模方法。赞分享文档教程示例工程【免费下载链接】CLRS:notebook:Solutions to Introduction to Algorithms项目地址https://gitcode.com/gh_mirrors/cl/CLRS点击查看免费下载相关推荐CLRS 第 21 章 21.1 练习精解用并查集Disjoint-Set实现连通分量算法 CONNECTED-COMPONENTSCLRS 第 21 章 21.1 练习精解用并查集Disjoint Set实现连通分量算法 CONNECTED COMPONENTS 导读 本节围绕《算法文档教程示例工程LeetCode-Go 题解 783Minimum Distance Between BST NodesBST 中序遍历求最小节点差值LeetCode Go 题解 783Minimum Distance Between BST NodesBST 中序遍历求最小节点差值 导读 LeetCo示例工程30 Seconds of Code 算法实战用节点度数在 JavaScript 中高效求解无向树的最小高度树Minimum Height Tree30 Seconds of Code 算法实战用节点度数在 JavaScript 中高效求解无向树的最小高度树Minimum Height Tree 在无教程文档上一篇5分钟掌握Illustrator批量替换神器ReplaceItems.jsx完整操作指南下一篇解读 Bitcoin 0.8.2 维护版发布说明手续费政策、JSON-RPC 与网络层演进附 Dogecoin 源码印证创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 CLRS 第 21 章实战：用并查集高效求解离线最小值问题（Off-line Minimum）
文档教程示例工程【免费下载链接】CLRS:notebook:Solutions to Introduction to Algorithms项目地址https://gitcode.com/gh_mirrors/cl/CLRS点击查看免费下载本文以《算法导论》CLRS第 21 章“Data Structures for Disjoint Sets”章末问题Problem 21-1Off-line minimum为核心完整讲解离线最小值问题的定义、同质子序列划分、OFF-LINE-MINIMUM算法伪代码、正确性证明以及如何用不相交集合并查集Union-Find数据结构将实现复杂度压缩到近线性的O(nα(n))。文中给出的实例推演、算法步骤与复杂度结论全部取自仓库文档 C21-Data-Structures-for-Disjoint-Sets/problem.md并结合作者整理的工程实现 uf.cpp 进行源码级验证。读完本文你将掌握“离线”场景下批量预测EXTRACT-MIN返回值的思想并能独立把这类问题映射到并查集上的MAKE-SET / FIND-SET / UNION操作。问题定义在“离线”前提下预测每次 EXTRACT-MIN 的返回值离线最小值问题off-line minimum problem要求维护一个动态集合 T元素来自定义域{1, 2, ..., n}其上仅支持两种操作INSERT向集合 T 中插入一个新键EXTRACT-MIN返回并删除 T 中的当前最小值。我们拿到一个操作序列 S其中包含n 次 INSERT和m 次 EXTRACT-MIN并且定义域{1, 2, ..., n}中的每个键恰好被插入一次。任务是为每次EXTRACT-MIN调用确定它返回的键即填充数组extracted[1..m]对i 1, 2, ..., mextracted[i]是第 i 次EXTRACT-MIN返回的键。所谓“离线”off-line是指我们被允许在处理整个序列 S 之后才逐个确定所有返回值——这与在线online场景相反在线场景要求在每次EXTRACT-MIN执行时就立即返回答案。离线的自由度给了我们优化空间可以一次性观察全部 INSERT 的落点再用合适的数据结构批量求解。手工推演一个 14 步实例的 extracted 数组问题 a文档给出了如下实例其中数字代表一次INSERT字母E代表一次EXTRACT-MIN4, 8, E, 3, E, 9, 2, 6, E, E, E, 1, 7, E, 5这里的 n 10键 1..10m 6共 6 次 E。EXTRACT-MIN的行为可以理解为每个 E 返回它之前出现、且尚未被返回过的最小值。逐次推演如下步骤已插入且未被取出的键本次 E 的返回值第 1 个 E{4, 8}4第 2 个 E{3, 8}3第 3 个 E{9, 2, 6, 8}2第 4 个 E{6, 8, 9}6第 5 个 E{8, 9}8第 6 个 E{1, 7, 9}1因此得到的答案数组为extracted [4, 3, 2, 6, 8, 1]注意键 5、7、9 在最后一次EXTRACT-MIN之后才插入或始终未被取出它们不会被写入extracted——这正对应下文算法中j m1的“不写入”分支。把序列切成同质子序列与集合 K_j为了把“离线”优势显式化文档将序列 S 表示为如下同质子序列homogeneous subsequences形式I1, E, I2, E, I3, ..., Im, E, Im1其中每个E代表一次EXTRACT-MIN调用而每个I_j代表一段可能为空的连续INSERT序列。对每个子序列I_j把其中插入的键放入一个集合K_j若I_j为空则K_j为空集。这样划分的关键观察是第 j 次EXTRACT-MIN只能从K_1 ∪ ... ∪ K_j中取值因为I_{j1}之后的键还没有被插入键i在算法中只关心它落在哪个 K_j 里——这天然地对应并查集“元素属于哪个集合”的语义。OFF-LINE-MINIMUM 算法伪代码与执行语义基于上述划分文档给出的核心算法如下OFF-LINE-MINIMUM(m, n) for i - 1 to n do determine j such that i ∈ K[j] if j ! m 1 extracted[j] i let l be the smallest value greater than j for which set K[l] exists K[l] K[j] ∪ K[l], destroying K[j] return extracted逐行语义解读determine j such that i ∈ K[j]按键从小到大i 1..n处理。每个键恰好属于一个K_j这一步回答“键 i 是在哪一段 INSERT 中进来的”。if j ! m 1若j m1说明键 i 是在最后一次EXTRACT-MIN之后才插入的永远不会被任何一次提取返回因此不写入extracted。extracted[j] i否则键 i 就是第 j 次提取的返回值。由于按从小到大处理键当处理到 i 时所有比 i 小的键都已正确分配完毕因此第 j 次提取“当前最小”必然轮到 i。合并取j之后第一个仍然存在的集合K_l最小的l j把K_j并入K_l并销毁K_j。这相当于“撤销”第 j 次提取K_j中剩余的键原本只能被第 j 次提取返回现在 j 已被分配这些键就只能顺延给后续的提取因此并入其后第一个“还活着”的集合是语义上最精确的转移。正确性证明问题 b文档给出的证明分为两步先证每个被写入的值都正确再证数组被完整填满。第一步写入的值正确。用归纳法。假设前i-1个整数即1, ..., i-1都已正确写入extracted现在处理整数 i。算法确定j使得i ∈ K_j——该 j 必然存在因为在任意截断点上 INSERT 的次数总是不少于 EXTRACT-MIN 的次数每次提取都必须有键可返回。若j m1则 i 在全部提取之后才插入不写入数组是正确行为。若j ≤ m则第 j 次提取恰好发生在I_j之后它必须返回 i因为所有比 i 小的键都已被正确分配给了更早的提取而 i 在I_j中才被插入不可能被第 j 次之前的任何提取返回。处理完 i 之后算法“消除”第 j 次提取将I_j与I_ll j且K_l尚未被合并过的最小者中的键合并。这给出一个语义等价的新序列被移除的提取已经把正确返回值1..i记录在案剩余待提取的键仍在剩余子序列中合并意味着I_j中的剩余键只能在尚未被移除的第 j 次之后的提取中被返回——这恰好解释了为什么要找“最小的、尚未合并的l j”。新序列与原序列产生相同的提取结果故算法输出的每次提取都正确。第二步数组完整填满。反证法。假设某一步存在最小的未被填充位置 j设其正确值为 i。由于 j 之前的每次提取都被正确填充其中必然不含 i。当算法处理整数 i 时集合K_j尚未被移除否则extracted[j]已被填充。键 i 位于 j 之前的某个插入子序列中因此当前它一定在K_1, ..., K_j的某一个集合里。若它在某个K_kk ≠ j中则算法会把extracted[k]填成 i这与“j 之前的所有位置均已正确填满”矛盾。因此i ∈ K_j算法把extracted[j]正确填成 i归纳完成数组必然被完整且正确地填满。用不相交集合实现高效 OFF-LINE-MINIMUM问题 c朴素实现中“determine j such that i ∈ K[j]”需要维护 n 个集合并在合并时重排代价很高。文档给出的方案是引入并查集不相交集合数据结构并为其集合代表representative额外维护三段元信息整数j该集合对应的编号即K_j的编号整数prev与next分别指向前一个、后一个尚未被合并的集合从而把所有存活的K_j组织成一条双向链表。初始化方式显然集合按K_0, K_1, ..., K_{m1}建立K_0的prev置为-1K_{m1}的next置为-1表示不存在。三种核心操作与伪代码的对应关系如下伪代码操作并查集实现说明determine j such that i ∈ K[j]一次FIND(i)随后读取代表节点上存储的编号 jFIND 定位 i 所在集合的代表编号字段即 jlet l be the smallest value j for which K[l] exists读取代表节点的next指针链表只保留未合并集合next就是最小的存活后继由于此时j ≠ m1next必然存在K[l] K[j] ∪ K[l], destroying K[j]一次UNION同时维护双向链表把被删除集合从链表中摘除再做传统的集合合并链表摘除的具体步骤对应文档第 6 行取出K_j代表的prev若存在把该前驱集合的next指向K_j代表的next前驱集合的“下一个”变成当前集合的“下一个”对称地取出K_j代表的next若存在把该后继集合的prev指向K_j代表的prev最后执行一次传统的UNION(K_j, K_l)——按并查集定义合并两个集合即可合并后新集合继承代表节点上的j / prev / next字段链表结构不受破坏。复杂度账目整个循环共执行恰好 n 次FIND每个键一次与恰好 m 次UNION每个K_j在算法运行中被删除且只删除一次。再加上初始化阶段的 n 次MAKE-SET在同时使用**按秩合并union by rank与路径压缩path compression**的前提下单次操作的摊还代价为O(α(n))于是总复杂度为O(n (nm)·α(n)) O(n·α(n))其中α(n)是增长极其缓慢的阿克曼反函数对任何实际规模的输入都可视为常数因此该实现在实践中是近线性的。复杂度背景为什么必须“按秩合并 路径压缩”并用O(nα(n))的结论依赖两种启发式同时生效。仓库文档 21.3.md 的习题 21.3-3 指出如果只用按秩合并、不做路径压缩可以构造一个含 n 次MAKE-SET、总共 m 次操作的操作序列其代价下界为Ω(m lg n)——即退化为对数级。该下界的构造如下见下图先执行 n 次MAKE-SET再执行2^⌊log₂n⌋ - 1次UNION按规则构建出一棵度为⌊log₂n⌋的二项树文中给出了度为 2 时的构建示例树的最深层节点值为 k最后连续执行m - n - 2^⌊log₂n⌋ 1次FIND-SET(k)每次查询沿最深层到根的路径走Θ(⌊log₂n⌋)步从而把整个序列的总时间下界推高到Ω(m lg n)。这解释了问题 c 的实现为何必须同时保留路径压缩只有按秩合并时树深可达Θ(lg n)而一旦叠加路径压缩摊还代价即从O(lg n)降到O(α(n))才支撑起OFF-LINE-MINIMUM的O(nα(n))总复杂度。仓库配套源码uf.cpp 中的工程化 Union-Find仓库为第 21 章提供了可直接编译运行的并查集实现 C21-Data-Structures-for-Disjoint-Sets/uf.cpp它在文档习题 21.3-2“写出带路径压缩的非递归 FIND-SET”中被引用为参考实现。核心类UF的关键设计如下class UF { private: vectorint parent; vectorint rank; int count; int N; int find(int p) { if (!validate(p)) return -1; while (p ! parent[p]) { parent[p] parent[parent[p]]; // path compression by halving p parent[p]; } return p; } void Union(int p, int q) { int rootP find(p); int rootQ find(q); if (rootP rootQ) return; // make root of smaller rank point to root of larger rank if (rank[rootP] rank[rootQ]) parent[rootP] rootQ; else if (rank[rootP] rank[rootQ]) parent[rootQ] rootP; else { parent[rootQ] rootP; rank[rootP]; } count--; } };对应到问题 c 的实现要点find采用路径折半压缩path compression by halving把沿途节点直接指向其祖父节点仅用迭代、无递归正是习题 21.3-2 要求的非递归版本Union采用按秩合并小秩树的根指向大秩树的根秩相等时深度加一count字段跟踪当前连通分量个数getCount()与connected(p, q)提供了与第 21.1 节CONNECTED-COMPONENTS算法一致的查询接口。若要在问题 c 的场景中落地该实现只需让UF的每个集合代表额外携带文档要求的j / prev / next三个字段即可把OFF-LINE-MINIMUM的第 2、4、6 行分别映射为find、next字段读取与Union并将count语义替换为“尚未被删除的K_j集合数”。仓库中 21.1.md 与 21.2.md 还分别用连通分量问题每次迭代调用FIND-SET共2|E|次、UNION共|V|-k次和链表表示 加权合并启发式从不同实现路线印证了并查集接口与复杂度分析的一致性。小结离线最小值问题展示了一个典型模式把“在线”必须即时回答的问题延后到“离线”批量处理从而用更强的数据结构换取更优的复杂度。其求解路径清晰可复现把操作序列切分为I1, E, I2, E, ..., Im, E, Im1并建立集合K_j按键从小到大执行OFF-LINE-MINIMUM每个键至多触发一次FIND和一次UNION用“代表节点携带 j/prev/next”的并查集实现使整体复杂度达到O(nα(n))。整套推导含实例答案[4,3,2,6,8,1]、正确性归纳证明与复杂度结论均可在仓库文档 C21-Data-Structures-for-Disjoint-Sets/problem.md 中核对工程实现可参考 uf.cpp。理解这一题之后处理“批量提取最小值”“离线批量查询”一类问题如按时间线预测队头出队元素时就能直接套用这套并查集 集合合并的建模方法。赞分享文档教程示例工程【免费下载链接】CLRS:notebook:Solutions to Introduction to Algorithms项目地址https://gitcode.com/gh_mirrors/cl/CLRS点击查看免费下载相关推荐CLRS 第 21 章 21.1 练习精解用并查集Disjoint-Set实现连通分量算法 CONNECTED-COMPONENTSCLRS 第 21 章 21.1 练习精解用并查集Disjoint Set实现连通分量算法 CONNECTED COMPONENTS 导读 本节围绕《算法文档教程示例工程LeetCode-Go 题解 783Minimum Distance Between BST NodesBST 中序遍历求最小节点差值LeetCode Go 题解 783Minimum Distance Between BST NodesBST 中序遍历求最小节点差值 导读 LeetCo示例工程30 Seconds of Code 算法实战用节点度数在 JavaScript 中高效求解无向树的最小高度树Minimum Height Tree30 Seconds of Code 算法实战用节点度数在 JavaScript 中高效求解无向树的最小高度树Minimum Height Tree 在无教程文档上一篇5分钟掌握Illustrator批量替换神器ReplaceItems.jsx完整操作指南下一篇解读 Bitcoin 0.8.2 维护版发布说明手续费政策、JSON-RPC 与网络层演进附 Dogecoin 源码印证创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考