路径压缩原理是啥?

P3367 【模板】并查集

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

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

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

by oisdoaiu @ 2020-11-25 22:06:05

@_Leaving

路径压缩难道不是一次就把祖先链全部搞成深度为1的点了吗/yiw


by oisdoaiu @ 2020-11-25 22:08:14

哦哦哦学到了


by 听取MLE声一片 @ 2020-11-25 22:20:18

@Lipail 后面一个根本没压,就像你记忆化搜索没有记录状态


上一页 |