Maximum Bipartite Matching (Boy-Girl Pairing)

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

Constraints: m, n can be up to a few hundred/thousand; grid entries are 0/1.

Example: grid = [[1,1,0],[1,0,1],[0,0,1]] Maximum matches = 3 (boy0-girl1, boy1-girl0, boy2-girl2).

Approach: This is the classic Maximum Bipartite Matching problem, solvable via the augmenting-path algorithm (Kuhn's algorithm): for each boy, attempt to find an augmenting path to an unmatched girl via DFS, reassigning previously matched girls recursively if it frees up a valid rematch - O(VE) overall. For larger inputs, Hopcroft-Karp improves this to O(Esqrt(V)) by finding multiple augmenting paths per phase via BFS+DFS.