Пост для тех, кому интересно научиться ещё быстрее искать паросочетание в двудольном графе.

Алгоритм Куна ищет паросочетание в двудольном графе за O(VE). Реализация, данная на emaxx, укладывается в такой шаблон:

forn(i, n) {
  fill(used, 0);
  dfs(i);
}

Я обычно пишу так:

fill(used, 0);
forn(i, n) 
  if (dfs(i))
    fill(used, 0);

То есть, обнуляю пометки только если нашёл дополняющую цепь. Теперь Кун работает за O(|M|·E), где |M| — размер максимального паросочетания.

Решение можно ускорить ещё как минимум в 2 раза, используя жадную инициализацию паросочетания. Идея: применяем Куна не к пустому паросочетанию, а к паросочетанию размера хотя бы |M| / 2. Кстати, |M| / 2 — оценка снизу, если перед жадной инициализацией сделать random_shuffle, жадность найдёт паросочетание чуть побольше, и Кун будет работать чуть быстрее.

Новое для меня

Оказалось, можно заставить Куна работать ещё в несколько раз быстрее...

fill(pair, -1);
for (int run = 1; run; ) {
  run = 0, fill(used, 0);
  forn(i, n)
    if (pair[i] == -1 && dfs(i))
      run = 1;
}

То есть, теперь я не обнуляю пометки даже если нашёл дополняющую цепь.

Я успел потестить на нескольких задачах, например, на задаче про доминошки. Эффект: новая идея без жадной инициализации в 3 раза быстрее старой идеи с жадной инициализацией. Можно скачать тесты и решения и поиграться самостоятельно. Думаете, в доминошках специфический граф? Потестил на произвольном двудольном графе, эффект "на макс тесте в 10 раз быстрее".

Мне эта модификация Куна чем-то напоминает Хопкрофта-Карпа, т.к. получается, что мы за O(E) находим не один путь, а несколько. Непонятно, что стало с асимптотикой алгоритма. Может быть, она тоже улучшилась?)

Спасибо за внимание.