这题是不是可以$O(n+m)$

YellowBean_Elsa @ 2020-02-17 20:59:07

by hater @ 2020-02-17 21:22:32

花好毒瘤啊

不会连并查集都要卡成log吧

by moongazer @ 2020-02-17 21:24:13

@hater 路径压缩或启发式合并都带log，只有两个优化都加才是\alpha(n)

by 引领天下 @ 2020-02-17 21:24:13

都是神仙Orz

by moongazer @ 2020-02-17 21:26:36

@hater 而且这个复杂度《算法导论》上有证明……而且是个远古结论

by hater @ 2020-02-17 21:27:15

@クトリ 大多数人不会这么写吧

窝只菜菜的用路径压缩

by xhQYm @ 2020-02-17 21:29:30

@YellowBean Orz您老

by zhanghengrui @ 2020-02-17 22:12:44

@皎月半洒花 路径压缩+按秩合并不是标配吗（反正只是复制粘贴板子的事）

by chenxinyang2006 @ 2020-02-17 22:37:57

其实按秩合并使用范围更广一点，复杂度理解也简单，为什么没有人用呢？

我至今都没有搞懂那个路径压缩的势能分析法是怎么弄的

by YellowBean_Elsa @ 2020-02-18 08:13:45

@皎月半洒花 不用并查集鸭

by YellowBean_Elsa @ 2020-02-18 08:14:42

巨佬们都写并查集的吗