compete::mcgill

Bipartite Matching (Kuhn)

O(V·E)

Maximum bipartite matching by repeatedly finding augmenting paths. Short and hard to break; fast enough up to a few thousand vertices. For tighter limits, run the Dinic template on the unit-capacity network instead, which gives O(E√V).

// use it on

CSES: School Dance ↗

Maximum boy-girl pairing given the allowed pairs: build the bipartite graph and read off max_matching() plus the matchL array.

// the code

struct Kuhn {  // left part 0..n-1, right part 0..m-1
    int n, m;
    vector<vector<int>> adj;  // adj[u] = right-side neighbours of left u
    vector<int> matchL, matchR;
    vector<bool> used;
    Kuhn(int n, int m) : n(n), m(m), adj(n), matchL(n, -1), matchR(m, -1) {}
    void add_edge(int u, int v) { adj[u].push_back(v); }
    bool try_kuhn(int u) {
        for (int v : adj[u]) {
            if (used[v]) continue;
            used[v] = true;
            if (matchR[v] == -1 || try_kuhn(matchR[v])) {
                matchL[u] = v;
                matchR[v] = u;
                return true;
            }
        }
        return false;
    }
    int max_matching() {
        int res = 0;
        for (int u = 0; u < n; u++) {
            used.assign(m, false);
            if (try_kuhn(u)) res++;
        }
        return res;
    }
};

// more matchings & flows

Dinic (Max Flow)Min-Cost Max-FlowHungarian Algorithm