Алгоритм Крускала и кишки лабиринтов

[domix32]

надо было box drawing characters использовать, а то очень сложно понимать что там за этими решётками. Да к тому же оно ещё и курсивное и в статье как картинка, а не как блок текста.

[asi8111]

Расскажите пожалуйста откуда у вас в базовом алгоритме Краскала взялась сложность - O(m^2 log m + n log m) . Сначала сортируем - получаем m*log(m). Далее идем по отсортированному списку ребер - и из каждой вершины - начала ребра пускаем dfs для определения циклов - (m+n). Итого - m*log(m) + m(m+n).

С учетом dsu, принимая сложность функции Акермана как O(1) получим m*log(m) + m.

Непонятно откуда взялось - m^2*log(m) - на каждом шаге пересортируете чтоли? Ни n*log(m) - это вообще непонятный член.