突然想明白了并查集的路径压缩,其实分成 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 的版本
在编程的修炼里
