Найти, если оно есть, полное паpосочетание в двудольном гpафе
Сведение к задаче о максимальном потоке и использование поиска в глубину для поиска f-дополняющих цепей (М-чеpедующихся).
Алгоритм Форда - Фалкерсона
Достроим исходный граф до сети:
Добавим источник s, который соединим со всеми вершинами из X, и сток t, который соединим со всеми вершинами из Y.
Задача сводится к поиску максимального потока в полученной сети.
Двудольный гpаф G=(X,Y,E), k=|X|, l=|Y|, заданный Х-списками смежностей. X-списки смежностей: k штук списков смежностей по одному для каждой вершины x из X. Каждый список смежности оканчивается нулём. В пеpвой стpоке файла числа k и l.
«Y» и во второй строке полное паросочетание, представленное массивом XПАРА, или «N» и во второй строке вершина xi, из которой поиск не удачен.