Алгоритм Куна

Лемма Бержа говорит о том, что паросочетание без увеличивающих цепей является максимальным.

Её важное следствие состоит в том, что максимальное паросочетание можно строить инкрементально, на каждом шаге делая поиск увеличивающей цепи и проводя её чередование.

Алгоритм Куна ровно в этом и заключается — начнем с пустого паросочетания и будем искать увеличивающие цепи, пока они ищутся.

Для поиска увеличивающей цепи можно мысленно построить граф, в котором из правой доли в левую можно идти только по рёбрам паросочетания, а из левой в правую — по любым. Тогда можно запустить поиск любого пути из свободной вершины левой доли в какую-нибудь свободную вершину правой доли в измененном графе, и ровно такой путь и будет увеличивающим.

Это можно делать как угодно — для упражнения автор рекомендует явно строить такой граф, искать путь любимым алгоритмом поиска и явно проводить чередования — однако устоялась эффективная реализация в виде dfs на 20 строчек кода, приведённая ниже.

const int maxn;

vector<int> g[maxn]; // будем хранить только рёбра из левой доли в правую
int mt[maxn]; // с какой вершиной сматчена вершина правой доли (-1, если ни с какой)
bool used[maxn]; // вспомогательный массив для поиска пути dfs-ом

// dfs возвращает, можно ли найти путь из вершины v
// в какую-нибудь вершину правой доли
// если можно, то ещё и проводит чередование
bool dfs(int v) {
    if (used[v])
        return false;
    used[v] = true;
    for (int u : g[v]) {
        // если вершина свободна, то можно сразу с ней соединиться
        // если она занята, то с ней можно соединиться только тогда,
        // когда из её текущей пары можно найти какую-нибудь другую вершину
        if (mt[u] == -1 || dfs(mt[u])) {
            mt[u] = v;
            return true;
        }
    }
    return false;
}

Теперь, для нахождения самого паросочетания нужно просто запустить этот поиск от всех вершин левой доли, откатывая состояние вспомогательного массива used:

memset(mt, -1, sizeof mt);
for (int i = 0; i < n; i++) {
    memset(used, 0, sizeof mt);
    if (dfs(i))
        cnt++;
}

Алгоритм ровно $n$ раз ищет увеличивающий путь, каждый раз просматривая не более $m$ рёбер, а значит суммарно отработает за $O(nm)$.

#Оптимизации

Что примечательно, алгоритм можно не бояться запускать на ограничениях и побольше ($n, m \approx 10^4$), если сделать некоторые неасимптотические оптимизации:

• Паросочетание можно жадно инициализировать — например, если просто заранее пройтись по вершинам левой доли и сматчить их со свободной вершиной правой, если она есть.
• Можно не заполнять нулями на каждой итерации массив used, а использовать следующий трюк: хранить в нём вместо булева флага версию последнего изменения, а конкретно — номер итерации, на которой это значение стало true. Если этот номер меньше текущего номера итерации, то мы можем воспринимать это значение как false. В каком-то смысле это позволяет эмулировать очищение массива за константу.
• Очень часто граф приходит из какой-то другой задачи, природа которой накладывает ограничения на его вид. Например, в задачах на решетках (когда есть двумерный массив, и соседние клетки связаны друг с другом) граф двудольный, но степень каждой вершины маленькая, и граф имеет очень специфичную структуру. На таких графах алгоритм Куша часто работает быстрее, чем ожидается из формулы $n \times m$. Контрпримеры в таких задачах почти всегда возможно сгенерировать, но авторы редко заморачиваются.

Подробнее про оптимизации можно почитать обсуждение здесь, но вообще говоря, увлекаться ускорением алгоритма Куна не стоит, потому что существует более асимптотически быстрый алгоритм. Задача нахождения максимального паросочетания — частный случай задачи о максимальном потоке, и если применить алгоритм Диница к двудольным графам с единичной пропускной способностью, то работать он будет за $O(m \sqrt n)$.