Что это такое?

Паросочетание — набор попарно несмежных рёбер графа.

Максимальное паросочетание — паросочетание, мощность которого максимальна среди всех возможных паросочетаний в данном графе.

Мощность паросочетания — количество рёбер в нём.

Как их находить? Существует алгоритм Куна, который основывается на поиске увеличивающихся цепей, пока ищется, и проведении чередования в них.

Код: C++ vector<vector>g; vectormatch; vectorused; bool kun(ll v) { if (used[v])return false; used[v] = true; for (auto& u : g[v]) { if (match[u] == -1) { match[u] = v; return true; } } for (auto& u : g[v]) { if (kun(match[u])) { match[u] = v; return true; } } return false; }

Где: g — списки смежности match[i] — вершина из левой доли, которая сопоставлена вершине i из правой доли used — была ли посещена вершина

Для нахождения максимального паросочетания необходимо произвести запуск данного алгоритма от каждой вершины левой доли (каждый раз надо чистить массив used).

Асимптотика — O(n*m)

P.S. Для ускорения я используется два раздельных цикла в самом алгоритме, т.к. сначала проверяются все вершины и ищется "несматченная" вершина, а это дает неплохое ускорение (только в частных случаях)