时间主要花在输入上了吧。
by qlzx74lyc41 @ 2022-08-19 19:36:10
@[qlzx74lyc41](/user/575453) 但是两个代码的时间只相差3ms,读入都是scanf
by _CowHorse_ @ 2022-08-19 19:37:05
@[chenye3](/user/541069) scanf输入很多数的时候也不会很快吧。
by qlzx74lyc41 @ 2022-08-19 19:38:58
@[qlzx74lyc41](/user/575453) 您可能理解错了,我在问为什么两个代码时间相差如此之小
by _CowHorse_ @ 2022-08-19 19:41:39
@[chenye3](/user/541069) 因为跑三四百万遍和一千万遍时间本来差距就不大。
by qlzx74lyc41 @ 2022-08-19 19:43:05
额,好吧
by _CowHorse_ @ 2022-08-19 19:44:44
@[chenye3](/user/541069) 实际上随机数据下只用路径压缩的并查集表现的已经足够优秀,但是还是有方法构造数据卡掉路径压缩。
by Fish9块1 @ 2022-08-19 19:50:44
比如 **使用二项树**
by Fish9块1 @ 2022-08-19 19:53:13
复杂度达到了上界,为logn,但是实际上已经够优秀了
by Fish9块1 @ 2022-08-19 19:54:30
实际上
> 路径压缩后的并查集几乎单次操作是0(1)的
by Fish9块1 @ 2022-08-19 19:55:39