Chapter 116

Refactoring: Hopcroft-Karp

Kuhn's DFS-based matching is O(V×E). Hopcroft-Karp uses BFS + DFS (like Dinic) to find multiple augmenting paths per phase — O(E√V). Much faster for large bipartite graphs.

Before: Kuhn's O(V×E)

C++ — O(V×E)

for (int u = 0; u < n; u++) { seen.assign(m, false); if (bpm(u)) result++; }

After: Hopcroft-Karp O(E√V)

C++ — Hopcroft-Karp

struct HopcroftKarp {
    vector> adj;
    vector pairU, pairV, dist;
    int n, m;  // left size, right size

    HopcroftKarp(int n, int m) : n(n), m(m), adj(n), pairU(n, -1), pairV(m, -1) {}

    void add_edge(int u, int v) { adj[u].push_back(v); }

    bool bfs() {
        queue q;
        dist.assign(n, -1);
        for (int u = 0; u < n; u++)
            if (pairU[u] == -1) { dist[u] = 0; q.push(u); }

        bool found = false;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                int pu = pairV[v];
                if (pu == -1) found = true;
                else if (dist[pu] == -1) {
                    dist[pu] = dist[u] + 1;
                    q.push(pu);
                }
            }
        }
        return found;
    }

    bool dfs(int u) {
        for (int v : adj[u]) {
            int pu = pairV[v];
            if (pu == -1 || (dist[pu] == dist[u] + 1 && dfs(pu))) {
                pairU[u] = v; pairV[v] = u; return true;
            }
        }
        dist[u] = -1;
        return false;
    }

    int max_matching() {
        int matching = 0;
        while (bfs())
            for (int u = 0; u < n; u++)
                if (pairU[u] == -1 && dfs(u)) matching++;
        return matching;
    }
};

// O(E√V) — standard for large bipartite graphs.