求助dalao

P3367 【模板】并查集

86158615777a @ 2018-08-08 21:08:09

为什么并查集用递归方式找根节点比用非递归方式快？

by HikariForever @ 2018-08-08 21:09:16

因为递归本来就很快啊

by Viston @ 2018-08-08 21:11:09

但容易爆栈

by HikariForever @ 2018-08-08 21:12:21

@HNFMS__viston 正解

by Juanzhang @ 2018-08-08 21:46:33

@四代目火影时间复杂度O(a(n))也深不到哪去吧（或许是我太蒻了

by Juanzhang @ 2018-08-08 21:47:37

@86158615777a 非递归常数小一些，但是比递归麻烦。

by HikariForever @ 2018-08-08 22:37:13

@小光递归不加记忆化的话很容易爆

by Juanzhang @ 2018-08-08 22:50:54

@四代目火影恐怕是路径压缩

by Juanzhang @ 2018-08-08 22:51:35

一般的并查集都带路径压缩吧（除了可持久化并查集

|