Problem link: https://www.geeksforgeeks.org/problems/maximum-bipartite-matching--170646/1

Problem Statement: There are M job applicants and N jobs. Each applicant has a subset of jobs that he/she is interested in. Each job opening can only accept one applicant and a job applicant can be appointed for only one job. Given a matrix G with M rows and N columns where G(i,j) denotes ith applicant is interested in the jth job. Find the maximum number of applicants who can get the job.

Input: M = 3, N = 5 G = {{1,1,0,1,1},{0,1,0,0,1}, {1,1,0,1,1}} Output: 3

Explanation:

There is one of the possible assignment- First applicant gets the 1st job. Second applicant gets the 2nd job. Third applicant gets the 4th job.

Constraints: 1 ≤ N, M ≤ 100

Help needed: I got to know about the solution which used maximum bipartite matching. However, I'm still unable to build an intuition about how that algo is working

I'll be grateful if someone can help me with some explanation/leads/articles ?

My Java Accepted code:

    private static final int NONE_SELECTED = -1;
    boolean rec(int p, int[][] interested, boolean[] explored, int[] selected) {
        int totalJobs =  interested[0].length;
        for(int j=0; j<totalJobs; j++) {
            if(interested[p][j] == 1 && !explored[j]) {
                explored[j] = true;
                if(selected[j] == NONE_SELECTED ||
                rec(selected[j], interested, explored, selected)) {
                    selected[j] = p;
                    return true;
                }
            }
        }
        
        return false;
    } 
    
    public int maximumMatch(int[][] g) {
        int totalJobs = g[0].length;
        int totalApplicants = g.length;
        int ans = 0;
        
        int[] selected = new int[totalJobs];
        Arrays.fill(selected, NONE_SELECTED);
        
        for(int p=0; p<totalApplicants; p++) {
            boolean[] explored = new boolean[totalJobs];
            Arrays.fill(explored, false); 
            if(rec(p, g, explored, selected) == true) ans++;
        }
        
        return ans;
    }