突然想明白了并查集的路径压缩,其实分成 2 步
root = fixedpoint(get_parent,p)
fixedpoint_list.for_each(x = root)
但是几乎 99% 的教程全是一步的,看了半天在一边递归一边压缩那里痛苦.
并查集这里的 iter 并不需要暴露出来(
虽然思想还是 iter_mut

Ken Kang, [03:44] 我感觉并查集的精髓是cache fixpoint, 你这个每次都要跑两次fixpoint不是吗
Asuka Minato, [03:45] 不是路径压缩吗
Asuka Minato, [03:45] 的确是多跑了一次(大概常数会 * 2
Asuka Minato, [03:54] 我其实也想过, 严格说是利用栈存了中间状态
Asuka Minato, [04:40] 哦对, 我那种写法没有栈空间😂
Asuka Minato, [04:41] 因为都是尾递归
Asuka Minato, [04:41] emm, 好像找到原因了(嘛, 大不了参数传个 arr 进去把结果带出来
Asuka Minato, [04:43] 所以要 cache 就一定会多占用空间 (无非是在哪里占用的.
带 arr cache 的版本

在编程的修炼里
notion image
 
Loading...
Steven Lynn
Steven Lynn
喂马、劈柴、周游世界
最新发布
我与 Dify 的半年
2025-3-9
我的2022年终小结
2024-11-9
记录雅思考试经历与一点学习心得
2024-11-9
Hackergame 2024 思路小结
2024-11-9
黑客松、日本、入职:我的2024下半年的总结
2024-11-9
NotionNext:基于Notion和NextJS的开源博客
2024-11-9