Хопкрофт — Карп

Алгоритм Куна ищет по одному увеличивающему пути за проход и стоит $O(VE)$. На сетках, досках и графах ходов коня, где вершин под сотню тысяч, это уже опасно.

Хопкрофт и Карп заметили, что за один проход можно найти сразу максимальный набор непересекающихся кратчайших увеличивающих путей — и что таких проходов нужно не больше $O(\sqrt V)$.

Почему проходов мало

Пусть после нескольких фаз кратчайший увеличивающий путь имеет длину $\ell$. Известно, что после каждой фазы эта длина строго растёт. С другой стороны, если максимальное паросочетание больше текущего на $k$, то симметрическая разность содержит $k$ непересекающихся увеличивающих путей, и хотя бы один из них короче $V / k$.

Значит, после $\sqrt V$ фаз до максимума остаётся не больше $\sqrt V$ увеличений, и каждое даёт ещё одну фазу. Итого $O(\sqrt V)$ фаз по $O(E)$ каждая.

Устройство фазы

Обход в ширину от всех свободных вершин левой доли по чередующимся рёбрам расставляет слои: $dist[u]$ — расстояние в чередующихся шагах. Если ни одной свободной вершины правой доли не достигли, паросочетание максимально.

Обход в глубину ищет увеличивающие пути, спускаясь строго по слоям: из $u$ разрешено идти в $v$, только если $dist[\,matchRight[v]\,] = dist[u] + 1$. Найденный путь сразу применяется, а вершины, из которых пути нет, помечаются как бесполезные до конца фазы.

while (bfs()) {                                  // слои
    for (int u = 0; u < leftCount; u++) iterator[u] = start[u];
    for (int u = 0; u < leftCount; u++)
        if (matchLeft[u] == -1 && tryAugment(u)) size++;
}

Две детали реализации

Указатель текущего ребра. Массив iterator хранит, до какого ребра вершина уже просмотрена в этой фазе. Без него фаза перестаёт быть линейной: одна и та же вершина будет перебирать своих соседей заново на каждом спуске.

Обход в глубину стеком, а не рекурсией. Длина увеличивающего пути доходит до числа вершин; на графе из ста тысяч вершин рекурсия — это отказ по памяти, а не по времени, и найти его труднее.

Когда что писать

вершин	рёбер	чем решать
до тысячи	любое	Кун без эвристик
до десятков тысяч	разреженный	Кун с жадным началом
сотни тысяч	любое	Хопкрофт — Карп
граф специально подобран против Куна	—	Хопкрофт — Карп

Жадное начальное паросочетание полезно и здесь: оно уменьшает число фаз, ничего не ломая.