쿤 알고리즘 - 알고리즘카

베르주 보조정리는 증가 경로가 없는 매칭이 최대 매칭이라는 것을 말해 줍니다.

이 보조정리의 중요한 따름정리는, 매 단계마다 증가 경로를 찾아 그 경로를 따라 교대를 수행함으로써 최대 매칭을 점진적으로 구성할 수 있다는 것입니다.

쿤 알고리즘은 바로 이것입니다. 빈 매칭에서 시작하여 증가 경로를 찾을 수 있는 동안 계속 찾아 나갑니다.

증가 경로를 찾기 위해, 오른쪽 파트에서 왼쪽 파트로는 매칭의 간선을 통해서만 이동할 수 있고, 왼쪽 파트에서 오른쪽 파트로는 어떤 간선으로든 이동할 수 있는 그래프를 머릿속으로 구성해 볼 수 있습니다. 그러면 변형된 그래프에서 왼쪽 부분의 자유 정점에서 오른쪽 부분의 어떤 자유 정점으로 가는 임의의 경로를 탐색할 수 있으며, 바로 그러한 경로가 증가 경로가 됩니다.

이 작업은 어떤 방식으로든 할 수 있습니다. 연습 삼아 저자는 이러한 그래프를 명시적으로 구성하고, 선호하는 탐색 알고리즘으로 경로를 찾고, 교대를 명시적으로 수행해 보기를 권장합니다. 하지만 아래에 제시된 20줄 남짓의 dfs 형태로 된 효율적인 구현이 정석으로 자리 잡았습니다.

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 배열을 0으로 채우는 대신 다음과 같은 트릭을 사용할 수 있습니다: 배열에 불리언 플래그 대신 마지막으로 변경된 버전, 구체적으로는 해당 값이 true가 된 반복의 번호를 저장합니다. 이 번호가 현재 반복 번호보다 작으면 그 값을 false로 간주할 수 있습니다. 어떤 의미에서 이는 배열을 상수 시간에 초기화하는 것을 흉내 낼 수 있게 해 줍니다.
그래프는 다른 어떤 문제에서 비롯되는 경우가 매우 많으며, 그 문제의 성질이 그래프의 형태에 제약을 가합니다. 예를 들어 격자 문제(2차원 배열이 있고 인접한 칸끼리 서로 연결된 경우)에서 그래프는 이분 그래프이지만, 각 정점의 차수가 작고 그래프가 매우 특수한 구조를 가집니다. 이러한 그래프에서 쿤 알고리즘은 $n \times m$ 공식으로 예상되는 것보다 빠르게 동작하는 경우가 많습니다. 이러한 문제에서도 반례는 거의 항상 만들어 낼 수 있지만, 출제자들이 굳이 그런 수고를 들이는 경우는 드뭅니다.

최적화에 대한 자세한 논의는 여기에서 읽어 볼 수 있지만, 일반적으로 말해 쿤 알고리즘의 가속에 너무 몰두할 필요는 없습니다. 점근적으로 더 빠른 알고리즘이 존재하기 때문입니다. 최대 매칭을 찾는 문제는 최대 유량 문제의 특수한 경우이며, 디닉 알고리즘을 용량이 1인 이분 그래프에 적용하면 $O(m \sqrt n)$에 동작합니다.