社区讨论

对并查集的疑惑

学术版参与者 6已保存回复 52

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
45 条
当前快照
1 份
快照标识符
@lqdr07mi
此快照首次捕获于
2023/12/20 20:26
2 年前
此快照最后确认于
2023/12/22 06:04
2 年前
查看原帖
感觉只启发式合并的并查集似乎没有用啊。我明明可以直接启发式合并并更改他的根。 这样查询复杂度O(1)O(1)的,修改复杂度O(log2n)O(log_2 n)的。
另外如果说先给出若干次连边,最后给出若干次查询问(在线)第i次修改后两个点是否在一个集合内的话,可以每次在自己的根被修改后插入一个时间戳,然后查询可以直接二分第一个在这之前的时间戳找到对应的根,这样空间复杂度一个log,时间一个log,查询时复杂度是loglog,似乎比主席树要优?
(蒟蒻纯口胡,错了勿喷)

回复

52 条回复,欢迎继续交流。

正在加载回复...