Задача о максимальном числе парасочетании

Формулировка задачи

В двудольном графе? выбрать максимальное количество ребер, непересекающихся по вершинам.

Первую долю будем называть девушками, а вторую парнями.

Будем брать ребра, пока беруться.
Построим следующий граф:
- От замужних дувушек ведет только одно ребро — к мужу. Пусть эти ребра красные.
- От остальных ребра оставим прежними.
WFS: Ищем путь в графе от холостой девушки к холостому парню.
- Для каждого найденного пути делаем преобразование графа:
  - Длина пути очевидным образом содержит нечетное число ребер 2n+1, причем через одно ребро красное — всего n красных ребер. Поменяем в этом пути красные ребра на некрасные, а красные сделаем красными. и GOTO WFS;

Сделует отметить прямую связь с задачей о максимальном потоке. Задача о паросочетаниях решается через максимальный поток:

Всех парней соединяем с источником A.
Всех девушек соединяем с стоком B.
Пропускная способность всех ребер {0,1} ( поток по любому ребру равен либо 1 либо 0).
Максимальный поток из A в B равен максимальному числу паросочетаний. Те ребра, по которым течет единичный поток и нужно брать.