Предистория

Недавно писал решение на свою задачу (ниже приложен мэшап, где она находится). Обычная задача на паросочетания, и в полученном графе очень быстро искалось максимальное паросочетание, что показалось мне странным (а также я не знаю как строго доказывать такую скорость) и поэтому я решил написать этот пост.

Краткая формулировка задачи

Дан ориентированный граф на $$$n$$$ вершинах и $$$m$$$ ребрах, нужно разбить граф на минимальное количество путей. Особенностью данного графа является то, что его диаметр $$$^\dagger$$$ можно оценить как $$$O(log(n))$$$.

$$$^\dagger$$$ Диаметром графа называется максимальное кратчайшее расстояние среди всех пар вершин.

Решение

Очевидно, что данная задача является учебной — нужно дублировать вершины и провести ребра графа в новом двудольном графе. Ответом будет $$$n - x$$$, где $$$x$$$ — максимальное паросочетание в получившемся двудольном графе.

Я приложу свой код алгоритма Куна, который содержит несколько оптимизаций.

int used[N];
int mt[N], timer = 1;
vector <int> g[N];
bool dfs (int u) {
    if (used[u] == timer) return false;
    used[u] = timer;
    for (int v: g[u]) {
        if (mt[v] == -1) {
            mt[v] = u;
            return true;
        }
    }
    for (int v: g[u]) {
        if (dfs(mt[v])) {
            mt[v] = u;
            return true;
        }
    }
    return false;
}
// ...
int main () {
    // ...
    for (int i = 0; i < n; ++i) {
        dfs(i);
        timer++;
    }
    // ...
}

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

• Хранение в массиве used значение timer'а, а не зануление used'ов каждый раз

• При запуске сначала ищем свободную вершину во второй доле, а потом ищем удлиняющую цепочку.

Почему так быстро?

Казалось бы, при ограничениях $$$n = 10^5, m = 10^6$$$ Кун будет работать $$$O(n \cdot m)$$$, что очень долго. Но на реальном графе Кун работает ~$$$100$$$ мс.

Лично я не знаю, как доказывать такую асимптотику, но моя гипотеза, что у Куна есть ограничение на количество проделанных операций. И данное ограничение можно оценить как $$$O((n + m) \cdot d)$$$, где $$$d$$$ — диаметр графа.

Вот ссылка на мэшап, где можно протестировать Куна.

Интересно услышать ваше мнение насчёт данной гипотезы.