@[lunjiahao](/user/779970)
哦哦，忘说了 Prim 是要加堆优化才有 $O(n \log n)$ 的
by lunjiahao @ 2024-05-27 20:26:20
@[ldh270657080](/user/1203411) kruskal 直接存边就行吧
by zjh114514 @ 2024-05-27 20:32:07
@[lunjiahao](/user/779970)
如果是二叉堆或者优先队列 Prim 复杂度是 $O((n+m) \log n)$ 吧。
要 $O(n \log n+m)$ 得斐波那契堆。
by yinianxingkong @ 2024-05-27 20:35:28
似乎优先队列优化的复杂度和 kruskal 一样是 $O(m \log m)$。
by yinianxingkong @ 2024-05-27 20:37:21
感觉理论上 kruskal 是会比 prim 慢一点，因为很多数据都是 $m>n$。
by Louis_lxy @ 2024-05-27 21:09:05
@[Igallta](/user/813622) 为啥你的记录无论是那个算法都比我的慢很多啊？感觉是你写法有问题。
by Louis_lxy @ 2024-05-27 21:11:09
@[ldh270657080](/user/1203411)
对的，因为您是大佬，您最强了。
by Igallta @ 2024-05-27 21:11:45
@[ldh270657080](/user/1203411) 优化后都是 $m \log m$！！！
而且你怎么推出 Kruskal 是 $m \log n$ 的，它是对边排序啊。。。
by dctc800d @ 2024-05-27 21:11:57
@[dctc800d](/user/735087) 算错了
by Louis_lxy @ 2024-05-27 21:13:43
@[dctc800d](/user/735087) 是 prim 不是 kruskal 啊
by Louis_lxy @ 2024-05-27 21:14:14