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);// ?? do we need this↵
if(rec(p, g, explored, selected) == true) ans++;↵
}↵
↵
return ans;↵
}↵
~~~~~↵
↵
↵
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;↵
}↵
~~~~~↵
↵
