Надзвичайно оригінальна задача про кістякове дерево#12856

Надзвичайно оригінальна задача про кістякове дерево (Розбір)

Коли у нас є задача, де потрібно знайти мінімальне кістякове дерево і ребра задані неявно, то часто буває корисно подумати в сторону алгоритму Борувки.

Далі йде приблизний опис алгоритму Борувки (для кращого розуміння погугліть):

У будь-який момент часу алгоритму наші вершини будуть розбиті на множини, причому вершини з однієї множини вже пов'язані між собою, а вершини з різних ні. Далі, ми повинні якимось чином знайти вагу мінімального ребра, що виходить з кожного числа й допровести ці ребра. Кількість множин зменшиться як мінімум в рази, тобто кількість ітерацій нашого алгоритму не більш логарифмічна від числа вершин.

Таким чином, все що нам залишилося, це вміти знаходити вагу мінімального ребра, що виходить з множини. Для цього, для кожного числа знайдемо інше число , таке що (a_i + a_j) \bmod M мінімально і числа належать різним множинам. Це можна робити зберігаючи всі числа в сеті, потім видаляти всі числа з однієї множини, знаходити для кожного з них оптимальне (за допомогою lower bound), повертати ці числа назад.