Изменения
→Идея алгоритма
<tex>E' = \{(s, u): u \in L\} \cup \{(u, v): u \in L, v \in R\ , (u, v) \in E\} \cup \{(v, t): v \in R\} </tex>.
Изначально максимальное текущее паросочетание пусто. На каждом шаге алгоритма будем поддерживать следующий инвариант: в него текущее найденное паросочетание входят те и только те ребра, ведущие которые направлены из <tex>L</tex> в <tex>R</tex>.
# Ищем в графе <tex>G'</tex> путь из <tex>s</tex> в <tex>t</tex> поиском в глубину.
# Если путь найден, перезаписываем текущее паросочетание. Теперь инвертируем все рёбра на пути (ребро <tex>(u, v)</tex> становится ребром <tex>(v, u)</tex> ) и удаляем <tex>(s, L)</tex> и <tex>(R, t)</tex> ребра, покрывающие вершины, принадлежащие текущему паросочетанию.
