Placment Of students

#include <bits/stdc++.h> 

// Make a function to check job available for that student or not

bool isJob(int id, vector<vector<int>>& mat, vector<int>& jobAlloted, vector<bool> check, int n){

    // Iterate over each job for this student

    for(int i=0; i<n; i++){

        // Check student job eligibility and already no job

        if(mat[id][i]==1 && !check[i]){

            check[i] = true;    // allot job 

            // if that job not alloted to anyone or if alloted, other job for that student available or not

            if(jobAlloted[i] == -1 || isJob(jobAlloted[i], mat, jobAlloted, check, n)){

                jobAlloted[i]=id;

                return true;

            }

        }

    }

    return false;

}

int maxMatch(vector<vector<int> > &mat) {

    int m = mat.size(), n = mat[0].size();

    // Number of job is fixed, to store which job corr. to which student

    vector<int> jobAlloted(n,-1);  

    int jobCount = 0;

    // Iterate over each student to allot a job

    for(int i=0; i<m; i++){

        vector<bool> check(n, false);

        if(isJob(i, mat, jobAlloted, check, n)){

            jobCount++;

        }

    }

    return jobCount;

}

Approach:

1. For each student, use a depth-first search (DFS) to find an augmenting path in the bipartite graph.
2. Keep track of the matching of students to jobs using an array.
3. Iterate through each student and attempt to find an augmenting path using DFS.
4. If an augmenting path is found, increment the count of placed students.
5. The maximum number of placed students will be the result.

Implementation:

1. Define a DFS function to find an augmenting path in the bipartite graph.
2. Initialize an array to keep track of the matching of students to jobs.
3. Iterate through each student, call DFS to find an augmenting path, and update the matching array.

#include <vector>

using namespace std;

bool dfs(int i, vector<vector<int>> &mat, vector<int> &match, vector<bool> &check, int n) {
    for (int j = 0; j < n; j++) {
        if (mat[i][j] == 1 && !check[j]) {
            check[j] = true;
            if (match[j] == -1 || dfs(match[j], mat, match, check, n)) {
                match[j] = i;
                return true;
            }
        }
    }
    return false;
}

int maxMatch(vector<vector<int>> &mat) {
    // Number of students and jobs
    int m = mat.size();
    int n = mat[0].size();

    // Matching array
    vector<int> match(n, -1);

    // Count of placed students
    int count = 0;

    // Iterate through each student
    for (int i = 0; i < m; i++) {
        // Visited array for DFS
        vector<bool> check(n, false);

        // If an augmenting path is found, increment count
        if (dfs(i, mat, match, check, n)) {
            count++;
        }
    }

    return count;
}

#include <bits/stdc++.h> ;
bool dfs(int i,vector<vector<int> > &mat,vector<int>&vis,vector<int>&dp){
    for(int j=0;j<mat[0].size();j++){
        if(mat[i][j] and dp[j]==0){
            dp[j]=1;
            if(vis[j]==-1 or dfs(vis[j],mat,vis,dp)){
                vis[j]=i;
                return true;
            }
        }
    }
    return false;
}
int maxMatch(vector<vector<int> > &mat) 
{
    int n=mat.size(),m=mat[0].size(),cnt=0;
    vector<int>vis(m,-1);
    for(int i=0;i<n;i++){
        vector<int>dp(m,0);
        if(dfs(i,mat,vis,dp)){
            cnt++;
        }
    }
    return cnt;
    
}

def asg(mat, u, n, vis, ch):
    for i in range(n):
        if mat[u][i] and not vis[i]:
            vis[i] = True
            if ch[i] < 0 or asg(mat, ch[i], n, vis, ch):
                ch[i] = u
                return True
    return False

def solve(n, m, mat):
    res = 0
    ch = [-1] * n

    for i in range(m):
        vis = [False] * n
        if asg(mat, i, n, vis, ch):
            res += 1

    return res

def maxMatch(mat):
    n = len(mat[0])
    m = len(mat)
    return solve(n, m, mat)

#include<bits/stdc++.h>

bool asg(vector<vector<int>> &mat,int u,int &n,vector<int> &vis,vector<int> &ch)

{

   for(int i=0;i<n;i++)

   {

       if(mat[u][i] && !vis[i])

       {

           vis[i]=true;

           if(ch[i]<0 || asg(mat,ch[i],n,vis,ch))

           {

               ch[i]=u;

               return true;

           }

           

       }

   }

   return false;

}

int solve(int n,int m,vector<vector<int>> &mat)

{

   int res=0;

   vector<int> ch(n,-1);

   

   for(int i=0;i<m;i++)

   {

       vector<int> vis(n,0);

       if(asg(mat,i,n,vis,ch))

           res++;

   }

   return res;

}

int maxMatch(vector<vector<int> > &mat)  

{

   int n=mat[0].size(),m=mat.size();

   return solve(n,m,mat);

}

I tried using the dp but not getting the correct output.

Hey everyone, creating this thread to discuss the interview problem - Placment Of students.

Practise this interview question on Coding Ninjas Studio (hyperlinked with the following link): Placment Of students