lab8.cpp

// A C++ program to find maximal
// Bipartite matching.
#include <iostream>
#include <string.h>
using namespace std;

// M is number of applicants
// and N is number of jobs
#define M 6
#define N 6

// A DFS based recursive function
// that returns true if a matching
// for vertex u is possible
bool bpm(bool bpGraph[M][N], int u,
		bool seen[], int matchR[])
{
	// Try every job one by one
	for (int v = 0; v < N; v++)
	{
		// If applicant u is interested in
		// job v and v is not visited
		if (bpGraph[u][v] && !seen[v])
		{
			// Mark v as visited
			seen[v] = true;

			// If job 'v' is not assigned to an
			// applicant OR previously assigned
			// applicant for job v (which is matchR[v])
			// has an alternate job available.
			// Since v is marked as visited in
			// the above line, matchR[v] in the following
			// recursive call will not get job 'v' again
			if (matchR[v] < 0 || bpm(bpGraph, matchR[v],
									seen, matchR))
			{
				matchR[v] = u;
				return true;
			}
		}
	}
	return false;
}

// Returns maximum number
// of matching from M to N
int maxBPM(bool bpGraph[M][N])
{
	// An array to keep track of the
	// applicants assigned to jobs.
	// The value of matchR[i] is the
	// applicant number assigned to job i,
	// the value -1 indicates nobody is
	// assigned.
	int matchR[N];

	// Initially all jobs are available
	memset(matchR, -1, sizeof(matchR));

	// Count of jobs assigned to applicants
	int result = 0;
	for (int u = 0; u < M; u++)
	{
		// Mark all jobs as not seen
		// for next applicant.
		bool seen[N];
		memset(seen, 0, sizeof(seen));

		// Find if the applicant 'u' can get a job
		if (bpm(bpGraph, u, seen, matchR))
			result++;
	}
	return result;
}

// Driver Code
int main()
{
	// Let us create a bpGraph
	// shown in the above example
	bool bpGraph[M][N] = {{0, 0, 0, 1, 1},
						{0, 0, 0, 1, 1},
						{0, 0, 0, 0, 1},
						{0, 0, 0, 0, 0, 0},
						{0, 0, 0, 0, 0, 0}};

	cout << "Maximum number of applicants that can get job is "
		<< maxBPM(bpGraph);

	return 0;
}