> For the complete documentation index, see [llms.txt](https://zhenchaogan.gitbook.io/leetcode-solution/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zhenchaogan.gitbook.io/leetcode-solution/leetcode-1820-maximum-number-of-accepted-invitations.md).

# LeetCode 1820. Maximum Number of Accepted Invitations

There are `m` boys and `n` girls in a class attending an upcoming party.

You are given an `m x n` integer matrix `grid`, where `grid[i][j]` equals `0` or `1`. If `grid[i][j] == 1`, then that means the `ith` boy can invite the `jth` girl to the party. A boy can invite at most **one girl**, and a girl can accept at most **one invitation** from a boy.

Return *the **maximum** possible number of accepted invitations.*

**Example 1:**

```
Input: grid = [[1,1,1],
               [1,0,1],
               [0,0,1]]
Output: 3
Explanation: The invitations are sent as follows:
- The 1st boy invites the 2nd girl.
- The 2nd boy invites the 1st girl.
- The 3rd boy invites the 3rd girl.
```

**Example 2:**

```
Input: grid = [[1,0,1,0],
               [1,0,0,0],
               [0,0,1,0],
               [1,1,1,0]]
Output: 3
Explanation: The invitations are sent as follows:
-The 1st boy invites the 3rd girl.
-The 2nd boy invites the 1st girl.
-The 3rd boy invites no one.
-The 4th boy invites the 2nd girl.
```

**Constraints:**

* `grid.length == m`
* `grid[i].length == n`
* `1 <= m, n <= 200`
* `grid[i][j]` is either `0` or `1`.

## Solution

[English Version in Youtube](https://youtu.be/70cuAeXs6rk)

[中文版解答Youtube Link](https://youtu.be/beVpSBo7FZk)

[中文版解答Bilibili Link](https://www.bilibili.com/video/BV1F5411A7dx/)

```
class Solution {
public:
    bool bipartiteMatch(const vector<vector<int>>& grid, int u, vector<bool> visited, vector<int>& girls) {
        int m = grid.size();
        int n = grid[0].size();
        for (int v = 0; v < n; v++) {
            if (grid[u][v] && !visited[v]) {
                visited[v] = true;
                if (girls[v] < 0 || bipartiteMatch(grid, girls[v], visited, girls)) {
                    girls[v] = u;
                    return true;
                }
            }
       }
       return false;
    }
    
    int maximumInvitations(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<int> grils(n, -1);
        int matches = 0;

        for (int u = 0; u < m; u++) {
            vector<bool> visited(n, false);
            if (bipartiteMatch(grid, u, visited, grils)) {
                matches++;
            }
        }
        return matches;
    }
};
```