1820. Maximum Number of Accepted Invitations (Maximum Bipartite Matching)
T: O(m * n^2)
S: O(n)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.
*/
```Last updated
