147
правок
Изменения
м
Нет описания правки
:* Разобьем граф на две доли;
:* Проходя по всем вершинам первой доли пытаемся найти увеличивающую цепь с началом в текущей вершине;
::* Если удается найти увеличивающую цепь, добавляем ребра выполняем чередование, то есть если ребро входило в цепь, то удалим его из этой цепи в паросочетаниепаросочетания, а если не входило, то наоборот добавим.
:* Найденное паросочетание и является максимальным.
