Тема: Краскал
http://e-maxx.ru/algo/mst_kruskal_with_dsu
if (rand() & 1) swap (a, b);
Этот if не меняет асимптотику. Может лучше его или убрать, или переписать на честные ранги? :-) Или конкретно в случае построения MST это действительно дает оптимайз?
P.S. Если нужен тест для произвольной СНМ-задачи, на котором этот "оптимайз" ничего не дает, могу предоставить.