Matching via Flow

class BipartiteMatching {
    constructor(L, R) {
        this.L = L; this.R = R;
        this.adj = Array.from({length: L}, () => []);
        this.matchL = new Array(L).fill(-1);
        this.matchR = new Array(R).fill(-1);
    }
    addEdge(u, v) { this.adj[u].push(v); }

    // Hopcroft-Karp: O(E√V)
    maxMatching() {
        let matching = 0;
        while (this._bfs()) {
            for (let u = 0; u < this.L; u++)
                if (this.matchL[u] === -1 && this._dfs(u)) matching++;
        }
        return matching;
    }

    _bfs() {
        this.dist = new Array(this.L).fill(Infinity);
        const queue = [];
        for (let u = 0; u < this.L; u++) {
            if (this.matchL[u] === -1) { this.dist[u] = 0; queue.push(u); }
        }
        let found = false;
        let i = 0;
        while (i < queue.length) {
            const u = queue[i++];
            for (const v of this.adj[u]) {
                const w = this.matchR[v];
                if (w === -1) found = true;
                else if (this.dist[w] === Infinity) {
                    this.dist[w] = this.dist[u] + 1;
                    queue.push(w);
                }
            }
        }
        return found;
    }

    _dfs(u) {
        for (const v of this.adj[u]) {
            const w = this.matchR[v];
            if (w === -1 || (this.dist[w] === this.dist[u] + 1 && this._dfs(w))) {
                this.matchL[u] = v; this.matchR[v] = u;
                return true;
            }
        }
        this.dist[u] = Infinity;
        return false;
    }
}