Placment Of students

It is possible that a single candidate is interested in multiple jobs but he can take up only one of the job out of his favourable jobs, also there is no priority in jobs, i.e all favourable jobs are equally favourable to the candidate

The first line of input contains an integer ‘T’ representing the number of test cases. Then the test cases follow. The first line of each test case contains 2 space-separated integers ‘M’ and ‘N’ which denote the number of applicants and number of jobs respectively. The next ‘M’ lines have ‘N’ space-separated binary numbers which denote the favourable jobs of each applicant.

Test Case 1: We see that we have 3 candidates and 2 jobs. Candidate 1 wants jobs 1 only Candidate 2 wants job 2 only Candidate 3 does not like any job So, with this given arrangement, we can have that candidate 1 gets a job1 and candidate 2 gets job 2. So we placed 2 candidates. Hence we return 2. Test Case 2: We have 4 candidates and 4 jobs Candidate 1 wants jobs 3 or jobs 4. Candidate 2 wants any of the 4 jobs (pretty desperate) Candidate 3 wants only job 4 Candidate 4 wants only job 1 So with this arrangement, we can have candidate 1 with job 3, candidate 2 with job 2 candidates 3 with job 4, and candidate 4 with job 1. Hence we placed all the candidates, hence we return 4.

DFS APPROACH

The key idea is to think of the problem as a bipartite graph where one side has nodes of applicants and the other side has nodes of jobs and the edges in the graph denote the relation between the jobs and candidate. (There is a directed edge between the candidate and job if the candidate wants that job.
Lets consider the following example:

0 1 1 0 0 0

1 0 0 1 0 0

0 0 1 0 0 0

0 0 1 1 0 0

0 0 0 0 0 0

0 0 0 0 0 1

The arrows in grey signify the ideal matches.
But how can this be achieved?
- We can achieve this by simply doing a depth-first search from each applicant node and see if any of his preferred jobs are available or not. We can keep track of assigned jobs using an ‘assign’ array and Keep the count of the number of people who have their jobs assigned.

We can take the following approach.

Make an array ‘assign’ which keeps track of assignment of jobs i.e what job is assigned to what person. Initially, it is -1 for all ‘N’ elements.
Make a variable ‘jobCount’ to keep track of the number of applicants placed.
Make all the jobs unvisited initially.
Then we loop through all the applicants and for each applicant we check all favorable jobs for that particular applicant and if we find a job which is either not assigned or if assigned to some other applicant, the other applicant has other jobs available, we assign the current job to that applicant.
We do this using a DFS like function that goes through the row of the current applicant and tries to assign one of his favorite jobs using the above-mentioned algorithm.
If we are able to assign a job to the applicant we increment the value of ‘jobCount’.
Finally, after traversing all nodes, we return the value of ‘jobCount’.

Time Complexity

O(N * M), where ‘N’ is the number of applicants and ‘M’ is the number of jobs available.

For each applicant, we do a DFS which will take the order of ‘M’ time and we do this for all ‘N’ applicants.

Space Complexity

O(N), where ‘N’ is the number of applicants

We need an array of size ‘N’ to keep track of jobs assigned

Problem statement

Sample Input 1:

Sample Output 1:

Explanation of Sample Input 1:

Sample Input 2:

Sample Output 2: