Алгоритм Куна для максимального паросочетания в двудольном графе — как и почему работает?

Идея. Перебираем вершины левой доли. Для каждой пытаемся найти увеличивающий путь — чередующуюся цепочку «свободное ребро → ребро паросочетания → свободное → ...», начинающуюся в свободной левой вершине и заканчивающуюся в свободной правой. Если нашли — «переключаем» рёбра вдоль пути, и размер паросочетания растёт на 1. Поиск пути — это DFS с попыткой «потеснить» уже занятые правые вершины.

int n, m; // размеры левой и правой доли
vector<vector<int>> adj; // adj[left] -> список right
vector<int> matchR; // matchR[right] = к какой left приписана, или -1
vector<char> used;

bool tryKuhn(int v){
    for(int to : adj[v]){
        if(used[to]) continue;
        used[to]=1;
        if(matchR[to]==-1 || tryKuhn(matchR[to])){
            matchR[to]=v;
            return true;
        }
    }
    return false;
}
int maxMatching(){
    matchR.assign(m,-1);
    int res=0;
    for(int v=0; v<n; v++){
        used.assign(m,0);
        if(tryKuhn(v)) res++;
    }
    return res;
}

Почему корректно: теорема Бержа — паросочетание максимально тогда и только тогда, когда в графе нет увеличивающего пути. Кун находит их все, значит результат максимален.

Асимптотика: $O(V \cdot E)$ — внешний цикл по $V$ вершинам, каждый запуск DFS обходит до $O(E)$ рёбер. Память $O(V+E)$.

Оптимизация: жадная инициализация (сначала ставим любые свободные пары до запуска основного цикла) часто ускоряет в разы на практике.