Bipartite Matching

C++ — maximum bipartite matching

vector> adj;
vector matchR;  // right → left matching
vector seen;

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

int max_matching(int n, int m) {  // n=left size, m=right size
    matchR.assign(m, -1);
    int result = 0;
    for (int u = 0; u < n; u++) {
        seen.assign(m, false);
        if (bpm(u)) result++;
    }
    return result;
}

// O(V × E) — use Hopcroft-Karp for larger graphs.