Maximum Bipartite Matching

Problem Given m boys and n girls at a party and an m x n grid where grid[i][j] == 1 means boy i may invite girl j, find the maximum number of boy-girl pairs that can be formed when each boy invites at most one girl and each girl accepts at most one invitation.

Input / Output

• Input: an m x n 0/1 compatibility grid.
• Output: an integer — the maximum number of simultaneous pairings (and optionally the pairing itself).

Constraints

• m, n up to a few hundred or thousand; entries are 0 or 1.
• Each boy matches at most one girl and vice versa — the matching must be one-to-one.
• The graph is bipartite by construction: edges only run between the two sides.

Example

• grid = [[1,1,0],[1,0,1],[0,0,1]] -> maximum matches = 3 (boy0-girl1, boy1-girl0, boy2-girl2).
• Tricky case: boy0 greedily taking girl0 would strand boy1, who has girl0 as his only other option — the algorithm must be able to reassign an already-matched girl, which is exactly what augmenting paths do.