# 1820. Maximum Number of Accepted Invitations
###### tags: `Leetcode` `Medium` `Graph` `Hungarian Algorithm`
Link: https://leetcode.com/problems/maximum-number-of-accepted-invitations/description/
## 思路
匈牙利算法[讲解](https://zhuanlan.zhihu.com/p/96229700)
按照上面的讲解找最大匹配即可
也可以看[这个](https://leetcode.com/problems/maximum-number-of-accepted-invitations/solutions/1978859/python-hungarian-algorithm-easy-to-understand/?orderBy=most_votes)
## Code

class Solution {
    int[] matches;
    public int maximumInvitations(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        matches = new int[n];
        Arrays.fill(matches, -1);
        boolean[] visited = new boolean[n];
        int cnt = 0;
        for(int i=0; i<m; i++){
            visited = new boolean[n];
            if(getMatch(i, visited, grid)) cnt++;
        }
        return cnt;
    }
    private boolean getMatch(int i, boolean[] visited, int[][] grid){
        for(int j=0; j<grid[0].length; j++){
            if(grid[i][j]==1 && !visited[j]){
                visited[j] = true;
                if(matches[j]==-1 || getMatch(matches[j], visited, grid)){
                    matches[j] = i;
                    return true;
                }
            }
        }
        return false;
    }
}