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

中文版解答Youtube Link

中文版解答Bilibili Link

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;
    }
};