1820. Maximum Number of Accepted Invitations (Maximum Bipartite Matching)

T: O(m * n^2)
S: O(n)

Interview Pearls: Maximum Bipartite MatchingLinkedInEditors

https://www.youtube.com/watch?v=beVpSBo7FZk

```java
class Solution {
    public int maximumInvitations(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[] girls = new int[n];
        Arrays.fill(girls, -1);

        int matches = 0;
        for (int i = 0; i < m; i++) { // for all boys
            boolean[] visited = new boolean[n];
            if (dfs(grid, i, girls, visited)) {
                matches++;
            }
        }
        return matches;
    }
    private boolean dfs(int[][] grid, int b, int[] girls, boolean[] visited) {
        int n = grid[0].length;
        for (int i = 0; i < n; i++) { // for all girls
            if (grid[b][i] == 0 || visited[i]) { // because we'll find again later
                continue;
            }

            visited[i] = true;
            if (girls[i] < 0 || dfs(grid, girls[i], girls, visited)) {
                girls[i] = b;
                return true;
            }
        }
        return false;
    }
}

/***

girl[-1,-1...]

match

-> if we can find pair -> match++

findPair()
for (all girls) -> to find pair
if (girl[g] < 0 || findPair(girl[g]) find another one 
return true;


The outer loop runs m times (for each boy).
For each boy, the dfs function tries to match with each girl, which is n times.
And in the worst case, the recursive DFS call can be called n times (exploring the entire grid for all possible augmenting paths).
The complexity does indeed multiply together to give O(m * n^2) for this implementation.
 */
```