Редактирование: Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 287: | Строка 287: | ||
add <tex>r</tex> '''to''' <tex>\mathtt{P}[j]</tex> | add <tex>r</tex> '''to''' <tex>\mathtt{P}[j]</tex> | ||
'''if''' <tex>|\mathtt{P}[j]| > |\mathtt{P}[i]|</tex> <font color=darkgreen>//Парный класс должен быть меньшего размера</font> | '''if''' <tex>|\mathtt{P}[j]| > |\mathtt{P}[i]|</tex> <font color=darkgreen>//Парный класс должен быть меньшего размера</font> | ||
− | <tex>\mathtt{swap}(\mathtt{P}[i],\ \mathtt{P}[j])</tex> <font color=darkgreen>//swap за <tex>\mathtt{O(1)}</tex> | + | <tex>\mathtt{swap}(\mathtt{P}[i],\ \mathtt{P}[j])</tex> <font color=darkgreen>//swap за <tex>\mathtt{O(1)}</tex> - просто переставить указатели</font> |
'''for''' <tex>r \in \mathtt{P}[j]</tex> <font color=darkgreen>//Обновляем номера классов для вершин, у которых они изменились</font> | '''for''' <tex>r \in \mathtt{P}[j]</tex> <font color=darkgreen>//Обновляем номера классов для вершин, у которых они изменились</font> | ||
<tex>\mathtt{Class}[r] = j</tex> | <tex>\mathtt{Class}[r] = j</tex> |