第一次听说桶优化，大佬教教
by scp020 @ 2024-04-13 10:34:44
O(nlogn)的sort优化为O(n)基数排序啊
by tzhengqing @ 2024-04-13 10:38:52
```cpp
for(int i=1;i<=10000;i++)
{
while(!f[i].empty())
{
++cnt;
e[cnt].v=f[i].front().v;e[cnt].x=f[i].front().x;e[cnt].y=f[i].front().y;
f[i].pop();
}
}
```
这一段不是O(n)吗??
by tzhengqing @ 2024-04-13 10:39:56
其实理论上你的并查集是 $O(\log n)$。如果说实际效率的话，stl 的 sort 是很快的
by vflower @ 2024-04-13 10:41:44
@[tzhengqing](/user/1058570) 复杂度是挺好看，但是你这个数据量太少了，体现不出来优势，而且我们其实真的用不到这样的排序方式，很多实际应用的时候的边权可能是浮点数，这种东西不能塞到桶里啊！加之 `std::sort` 的效率本来就被压榨到极限了，`std::vector` 插入元素还需要扩展自身，效率上肯定不能太理想。
另外，什么都用复杂度分析只会害了你！
by Terrible @ 2024-04-13 10:41:50
@[vflower](/user/1000066) @[Terrible](/user/195942) 感谢，膜拜巨佬
by tzhengqing @ 2024-04-13 10:43:47
看错了，`std::queue` 容器选用的是 `std::deque`，`std::deque` 也不是给你当桶用的啊。。。这怎么可能会快？
by Terrible @ 2024-04-13 10:44:42