← all categories

Bipartite Matching 758317fb

Maximum bipartite matching via augmenting paths (Kuhn's). Left side has nLeft nodes (0-indexed), adj[u] lists right-side neighbors; matchR[v] = matched left node or -1. Slower than Hopcroft-Karp in the worst case but much shorter to type.

Time: O(V \cdot E). tested

content/flows/bipartite-matching.h

struct BipartiteMatching {
    int nLeft, nRight;
    vector<vector<int>> adj;
    vector<int> matchL, matchR;
    vector<bool> vis;

    BipartiteMatching(int nLeft, int nRight) : nLeft(nLeft), nRight(nRight), adj(nLeft), matchL(nLeft, -1), matchR(nRight, -1) {}

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

    bool tryKuhn(int u) {
        for (int v : adj[u]) {
            if (vis[v]) continue;
            vis[v] = true;
            if (matchR[v] == -1 || tryKuhn(matchR[v])) {
                matchL[u] = v; matchR[v] = u;
                return true;
            }
        }
        return false;
    }

    int maxMatching() {
        int res = 0;
        for (int u = 0; u < nLeft; u++) {
            vis.assign(nRight, false);
            if (tryKuhn(u)) res++;
        }
        return res;
    }
};