##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1820.html

# 1820. Maximum Number of Accepted Invitations

Medium

## Description

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 i-th boy can invite the j-th 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

Use backtrack. For each boy, find a girl that matches the boy, and the number of accepted invitations is added by 1 if such a match is found. Finally, return the maximum number of accepted invitations.

• class Solution {
int maxInvitations = 0;

public int maximumInvitations(int[][] grid) {
int rows = grid.length, columns = grid[0].length;
int[] matches = new int[columns];
Arrays.fill(matches, -1);
for (int i = 0; i < rows; i++) {
boolean[] visited = new boolean[columns];
if (backtrack(grid, i, visited, matches))
maxInvitations++;
}
return maxInvitations;
}

public boolean backtrack(int[][] grid, int row, boolean[] visited, int[] matches) {
int columns = visited.length;
for (int j = 0; j < columns; j++) {
if (grid[row][j] == 1 && !visited[j]) {
visited[j] = true;
if (matches[j] == -1 || backtrack(grid, matches[j], visited, matches)) {
matches[j] = row;
return true;
}
}
}
return false;
}
}

############

class Solution {
private int[][] grid;
private boolean[] vis;
private int[] match;
private int n;

public int maximumInvitations(int[][] grid) {
int m = grid.length;
n = grid[0].length;
this.grid = grid;
vis = new boolean[n];
match = new int[n];
Arrays.fill(match, -1);
int ans = 0;
for (int i = 0; i < m; ++i) {
Arrays.fill(vis, false);
if (find(i)) {
++ans;
}
}
return ans;
}

private boolean find(int i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1 && !vis[j]) {
vis[j] = true;
if (match[j] == -1 || find(match[j])) {
match[j] = i;
return true;
}
}
}
return false;
}
}

• // OJ: https://leetcode.com/problems/maximum-number-of-accepted-invitations/
// Time: O(?)
// Space: O(N)
class Solution {
public:
int maximumInvitations(vector<vector<int>>& A) {
int M = A.size(), N = A[0].size(), ans = 0;
vector<int> match(N, -1);
vector<bool> seen;
function<bool(int)> dfs = [&](int u) {
for (int v = 0; v < N; ++v) {
if (!A[u][v] || seen[v]) continue; // If there is no edge between (u, v), or this girl is visited already, skip
seen[v] = true;
if (match[v] == -1 || dfs(match[v])) {
match[v] = u;
return true;
}
}
return false;
};
for (int i = 0; i < M; ++i) { // Try each node as the starting point of DFS
seen.assign(N, false);
if (dfs(i)) ++ans;
}
return ans;
}
};

• class Solution:
def maximumInvitations(self, grid: List[List[int]]) -> int:
def find(i):
for j, v in enumerate(grid[i]):
if v and j not in vis:
if match[j] == -1 or find(match[j]):
match[j] = i
return True
return False

m, n = len(grid), len(grid[0])
match = [-1] * n
ans = 0
for i in range(m):
vis = set()
ans += find(i)
return ans


• func maximumInvitations(grid [][]int) int {
m, n := len(grid), len(grid[0])
var vis map[int]bool
match := make([]int, n)
for i := range match {
match[i] = -1
}
var find func(i int) bool
find = func(i int) bool {
for j, v := range grid[i] {
if v == 1 && !vis[j] {
vis[j] = true
if match[j] == -1 || find(match[j]) {
match[j] = i
return true
}
}
}
return false
}
ans := 0
for i := 0; i < m; i++ {
vis = map[int]bool{}
if find(i) {
ans++
}
}
return ans
}