照理说时间复杂度一样
by King_of_gamers @ 2019-01-09 11:39:35
而且这题我是随机合并的，跑的挺快哈
by King_of_gamers @ 2019-01-09 11:40:05
是一样的，肯定你写挂了
by 小粉兔 @ 2019-01-09 11:49:31
是一样的，肯定你写挂了
by Flaranis @ 2019-01-09 13:04:53
是一样的，肯定你写挂了
by λᴉʍ @ 2019-01-09 13:09:22
是一样的，肯定你写挂了
by 142857cs @ 2019-01-09 14:09:37
是一样的，肯定你写挂了
by Tsumi @ 2019-01-23 16:26:35
说一样的不要乱带节奏。不要误导萌新。
我当年并查集这里理解了很久，印象深刻。
按秩合并和按size合并都是一种“启发式策略”，而我们一般说的“启发式合并”指的是按size合并。
一般并查集，只采用按秩合并就能够保证复杂度严格不超过$O(\log n)$。
因为在这种策略下，节点深度是不会超过$\lceil\log n\rceil$的。
我就不严格证明了，简单口胡一下。
考虑让一个点的秩增大，当且仅当我们用另一个秩一样的集合合并它。
换句话说，我们要得到秩为$k$的集合，就需要至少两个秩为$k-1$的集合。而每个集合又需要至少两个小一点的集合合并得到。
所以$n$个点的集合深度最坏情况下是：$Deep(n)=Deep(n/2)+1=O(\log n)$
而按照size合并的话，如果不路径压缩，是没有办法保证深度的。
就是说，如果询问到了深度较大的节点，您就被卡了。@[suwakow](/space/show?uid=102506)
另外，您的期望复杂度也是$O(\log n)$，不过按照期望算出来的常数有点大。@[炜哥](/space/show?uid=28810)
by _meaningless_ @ 2019-01-24 16:49:41
@[zxyoi](/space/show?uid=46382) 啊 谢谢您
不过我的ac代码严格来说也不是按秩合并？我是按照最大深度合并的(:3_ヽ)_
by suwakow @ 2019-01-25 20:12:36
@[zxyoi](/space/show?uid=46382) 按size合并真的是可以的
by 142857cs @ 2019-01-25 20:48:54