社区讨论
对并查集的疑惑
学术版参与者 6已保存回复 52
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 45 条
- 当前快照
- 1 份
- 快照标识符
- @lqdr07mi
- 此快照首次捕获于
- 2023/12/20 20:26 2 年前
- 此快照最后确认于
- 2023/12/22 06:04 2 年前
感觉只启发式合并的并查集似乎没有用啊。我明明可以直接启发式合并并更改他的根。
这样查询复杂度的,修改复杂度的。
另外如果说先给出若干次连边,最后给出若干次查询问(在线)第i次修改后两个点是否在一个集合内的话,可以每次在自己的根被修改后插入一个时间戳,然后查询可以直接二分第一个在这之前的时间戳找到对应的根,这样空间复杂度一个log,时间一个log,查询时复杂度是loglog,似乎比主席树要优?
(蒟蒻纯口胡,错了勿喷)
回复
共 52 条回复,欢迎继续交流。
正在加载回复...