路径压缩原理是啥？

P3367 【模板】并查集

Lipail @ 2020-11-25 21:57:12

我看着这两种写法没啥太大差别啊，为什么前面能过后面 TLE 三个点？

return f[k]=ffind(f[k]);//return ffind(f[k])

by _5011_ @ 2020-11-25 21:57:57

保持树高在 O(\log n) 以内

by FutureThx @ 2020-11-25 21:58:42

把一个集合下的节点的父亲都设成祖先节点

by jerry3128 @ 2020-11-25 21:58:47

~~logn~~ 不是按秩合并吗（（

by _5011_ @ 2020-11-25 21:59:40

只加路径压缩是 O(logn)，只加按秩合并也是 O(logn)，两个同时加才是 O(α(n))

by Forever1507 @ 2020-11-25 21:59:55

把树压扁就是原理呀

by LeavingZzz @ 2020-11-25 22:02:28

但是第一种写法在递归之后会把 $1$ 变成 $3$ 的直接儿子，之后再找的话能少用一次递归这是 $n$ 比较小的例子，如果 $n$ 比较大的话这种优化效果非常显著也就是楼上说的保持树高（最长的链长度）在 $O(\log n)$ 以内

by jerry3128 @ 2020-11-25 22:02:42

@Zephyr_ ~~emm~~ 路径压缩不就直接反阿克曼函数了吗?(或者我学错了((((

by _5011_ @ 2020-11-25 22:03:38

@jerry3128 好像tarjan的论文给的复杂度是这个

by jerry3128 @ 2020-11-25 22:04:07

@Zephyr_ 学到了（

by StudyingFather @ 2020-11-25 22:05:48

@jerry3128 https://oi-wiki.org/ds/dsu-complexity/

| 下一页