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

Идея

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

Заметим, что через одну вершину может проходить только одна удлиняющая цепь. Тогда мы можем найти все удлиняющие цепи, запуская поиск удлиняющей цепи из каждой вершины. Искать удлиняющие цепи мы умеем DFS-ом.

Алгоритм

Давайте пройдемся по всем вершинам первой доли, проверяя насыщена ли текущая вершина(взято ли в паросочетание ребро, инцидентное ей), если насыщена - пропускаем, иначе пробуем насытить следующим DFS-ом:

 1 bool dfs (int v) {
 2     if (used[v]) {
 3         return false;
 4         used[v] = true;
 5         for (auto to : g[v]) {
 6             if (mt[to] == -1 || dfs(mt[to])) {
 7                 mt[to] = v;
 8                 return true;
 9 	    }
10     }
11     return false;
12 }

В DFS-е мы проверяем все ребра из вершины и если есть вершина, которая еще не насыщена, то мы нашли удлиняющую цепь, иначе запустимся и проверим, есть ли удлиняющая цепь и там.

Асимптотика

Мы запускаем DFS из всех вершин, то есть итоговая асимптотика - $O(N \cdot (N + M)$

Оптимизации

Несмотря на достаточно быструю константу(очень часто алгоритм Куна работает настолько быстро, что заходит и при $N = 2e5$, есть несколько его основных оптимизаций :

1) Брать не пустое паросочетание, а например набирать его жадно.

2) Очень часто можно столкнуться с тем, что не все вершины посещаются в DFS и поэтому каждый раз обнулять used - долго и можно просто хранить int в used и проверять что он равен номеру вершины, из которой мы запустили DFS :

 1 bool dfs (int v, int now) {
 2     if (used[v] == now) {
 3         return false;
 4         used[v] = true;
 5         for (auto to : g[v]) {
 6             if (mt[to] == -1 || dfs(mt[to], now)) {
 7                 mt[to] = v;
 8                 return true;
 9 	    }
10     }
11     return false;
12 }

Что дальше

Существует способ искать паросочетания быстрее($E\sqrt{V}$)(Потоки), также существуют способы искать взвешенное паросочетания и паросочетания не в двудольных графах(Сжатие соцветий)

---

Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin