求问并查集的时间复杂度

P3367 【模板】并查集

Drinkkk @ 2018-08-08 21:00:27

RT~~，今天闲来无事去看了一下并查集的时间复杂度~~。貌似网上的上界都是O(n \alpha(n))，请问各位dalao\alpha(10^7)等于多少，可以给一下求的方法吗？~~我才不会告诉你我在网上没有找到呢~~

by chen_zhe @ 2018-08-08 21:02:59

@钟梓俊 4

by chen_zhe @ 2018-08-08 21:03:35

@钟梓俊 \alpha(2^{65536})=5 我记得

by Tiphereth_A @ 2018-08-08 21:04:51

反阿克曼函数，把它当成常数就好，__int128范围内都不会超过4

by XiaoX @ 2018-08-08 21:05:56

摘自@lydrainbowcat 算法竞赛

对于任意N<2^{2^{10^{19729}}},都有 \alpha(N)<5

by Viston @ 2018-08-08 21:10:18

捕捉前排一群巨佬&&兜售旺旺酥绿鸟旺仔绿鸟糖旺旺仙鸟旺旺雪鸟旺仔小馒头绿鸟味

by Drinkkk @ 2018-08-08 21:21:16

@chen_zhe @khong @XiaoX 谢谢~

by nothingness @ 2018-09-07 18:12:01

@XiaoX 请问有没有具体证明方式？

by XiaoX @ 2018-09-07 21:00:58

@nothingness tarjan的神奇证明qwq

by Leap_Frog @ 2019-07-27 09:55:34

考古