知识卡片
离线祖先查询借并查集遍历
离线 LCA 过程按树递归:
- 进入节点时建集并记当前祖先,
- 处理每个孩子后合并集合、把合并后代表元的 ancestor 重新指向当前节点;
- 节点完成标黑后,对已标黑的查询端点读取其集合 ancestor。
原文留下正确性证明任务。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第19章 不相交集合的数据结构 · 查看原书依据
LCA(u) 1 MAKE-SET(u) 2 FIND-SET(u).ancestor = u 3 for each child v of u in T 4 LCA(v) 5 UNION(u, v) 6 FIND-SET(u).ancestor = u 7 u.color = BLACK 8 for each node v such that {u, v} ∈ P 9 if v.color == BLACK 10 print “The lowest common ancestor of” u “and” v “is” FIND-SET(v).ancestor
参考来源
- 位置:《算法导论(第4版)》第19章《不相交集合的数据结构》(OEBPS/chapter019.xhtml,文本字符[45000,47985))。
- 结论依据:章末LCA伪代码给出建集、孩子递归、合并、ancestor更新与已完成端点查询。
- 原始内容:LCA( u ) 1 M AKE -S ET ( u ) 2 F IND -S ET ( u ). ancestor = u 3 for each child v of u in T 4 LCA( v ) 5 U NION ( u , v ) 6 F IND -S ET ( u ). ancestor = u 7 u . color = BLACK 8 for each node v such that { u , v } ∈ P 9 if v . color == BLACK 10 print “The lowest common ancestor of” u “and” v “is” F IND -S ET ( v ). ancestor