好久不练最小生成树，最近开始复习的时候想到的问题
by ___I_AK_IOI @ 2018-08-30 11:48:34
kruskal
by ylxmf2020 @ 2018-08-30 11:50:35
kruskal
by 兮水XiShui丶 @ 2018-08-30 11:52:04
kruskal
by JYTS @ 2018-08-30 11:54:46
kruskal最棒！$O(m)$ 大法好！
by AThousandSuns @ 2018-08-30 11:54:55
关于稠密图是Prim,一般是Krukal吧
by zybnxy @ 2018-08-30 11:55:12
@[AThousandSuns](/space/show?uid=72118) 排序是 $O(m \log m)$ ， 并查集是 $O(m \log n)$ 或者是 $O(m \alpha(n))$，$O(m)$怎么做到的。。
by Gypsophila @ 2018-08-30 11:57:29
@[ACの666](/space/show?uid=54745) 哦有点道理，那就 $O(m\alpha(m))$ 吧（基数排序可以 $O(m)$）
by AThousandSuns @ 2018-08-30 12:00:47
@[AThousandSuns](/space/show?uid=72118) 最小生成树用基数排序的dalao%%%
by Gypsophila @ 2018-08-30 12:02:09
@[AThousandSuns](/space/show?uid=72118) 然而并查集同时使用路径压缩和按秩合并的复杂度也可以做大O(m)的
by creed_ @ 2018-08-30 12:03:42