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 i^{th }applicant is interested in the j^{th }job. Find the maximum number of applicants who can get the job.
Example 1:
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.
Example 2:
Input:
M = 6, N = 2
G = {{1,1},{0,1},{0,1},{0,1},
{0,1},{1,0}}
Output: 2
Explanation: There is one of the possible
assignment-
First applicant gets the 1st job.
Second applicant gets the 2nd job.
 
Your Task:
You don't need to read to print anything. Your task is to complete the function maximumMatch() which takes matrix G as input parameter and returns the maximum number of applicants who can get the job.
Expected Time Complexity: O(N^{3}).
Expected Auxiliary Space: O(N).
Constraints:
1 ≤ N, M ≤ 100

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Graph algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

	def maximumMatch(self, G):

		#code here

Solutions:
class Solution:

	def maximumMatch(self, G):
		M = len(G)
		N = len(G[0])
		ans = self.fun(G, M, N)
		return ans

	def fun(self, G, M, N):
		match = [-1 for i in range(N)]
		res = 0
		for u in range(M):
			seen = [False for i in range(N)]
			if self.bpm(G, u, seen, match, M, N):
				res += 1
		return res

	def bpm(self, G, u, seen, match, M, N):
		for v in range(N):
			if G[u][v] == 1 and (not seen[v]):
				seen[v] = True
				if match[v] < 0 or self.bpm(G, match[v], seen, match, M, N):
					match[v] = u
					return True
		return False


class Solution:

	def applyJobs(self, applicant, G, get_a_job, applyed):
		for i in range(len(G[0])):
			if G[applicant][i] and (not applyed[i]):
				applyed[i] = True
				if get_a_job[i] == -1 or self.applyJobs(get_a_job[i], G, get_a_job, applyed):
					get_a_job[i] = applicant
					return True
		return False

	def maximumMatch(self, G):
		applicants = len(G)
		jobs = len(G[0])
		numberOfcount = max(applicants, jobs)
		get_a_job = [-1] * jobs
		ans = 0
		for i in range(applicants):
			applyed = [False] * jobs
			if self.applyJobs(i, G, get_a_job, applyed):
				ans += 1
		return ans


class Solution:

	def maximumMatch(self, G):
		m = len(G)
		n = len(G[0])
		memo = [-1 for _ in range(max(n, m))]
		ans = 0

		def try_assign(i):
			for j in range(n):
				if G[i][j] == 1 and j not in seen:
					seen.add(j)
					if memo[j] < 0 or try_assign(memo[j]):
						memo[j] = i
						return True
			return False
		for i in range(m):
			seen = set()
			if try_assign(i):
				ans += 1
		return ans


class Solution:

	def maximumMatch(self, G):
		(M, N) = (len(G), len(G[0]))
		match = [-1] * N
		adjs = [[i for (i, v) in enumerate(G[u]) if v == 1] for u in range(M)]

		def _dfs(u, vis):
			for v in adjs[u]:
				if vis[v]:
					continue
				vis[v] = True
				if match[v] == -1 or _dfs(match[v], vis):
					match[v] = u
					return True
			return False
		for u in range(M):
			vis = [False] * N
			_dfs(u, vis)
		return sum((v > -1 for v in match))


class Solution:

	def try_kunh(self, u, G, used, mt):
		for v in range(len(G[0])):
			if G[u][v] and used[v] == False:
				used[v] = True
				if mt[v] < 0 or self.try_kunh(mt[v], G, used, mt):
					mt[v] = u
					return True
		return False

	def maximumMatch(self, G):
		m = len(G)
		n = len(G[0])
		N = max(n, m)
		ans = 0
		mt = [-1 for i in range(N)]
		for i in range(m):
			used = [False for j in range(N)]
			if self.try_kunh(i, G, used, mt):
				ans = ans + 1
		return ans


class Solution:

	def maximumMatch(self, G):
		(m, n) = (len(G), len(G[0]))
		match = [-1] * n
		visited = [False] * n

		def dfs(i):
			for j in range(n):
				if G[i][j] and (not visited[j]):
					visited[j] = True
					if match[j] == -1 or dfs(match[j]):
						match[j] = i
						return True
			return False
		count = 0
		for i in range(m):
			visited = [False] * n
			if dfs(i):
				count += 1
		return count


class Solution:

	def maximumMatch(self, G):
		matched = [-1] * len(G[0])
		ans = 0

		def dfs(u, visited):
			for (i, v) in enumerate(G[u]):
				if v == 1 and i not in visited:
					visited.add(i)
					if matched[i] == -1 or dfs(matched[i], visited):
						matched[i] = u
						return True
			return False
		for (u, _) in enumerate(G):
			if dfs(u, set()):
				ans += 1
		return ans


class GFG:

	def __init__(self, graph):
		self.graph = graph
		self.ppl = len(graph)
		self.jobs = len(graph[0])

	def bpm(self, u, matchR, seen):
		for v in range(self.jobs):
			if self.graph[u][v] and seen[v] == False:
				seen[v] = True
				if matchR[v] == -1 or self.bpm(matchR[v], matchR, seen):
					matchR[v] = u
					return True
		return False

	def maxBPM(self):
		matchR = [-1] * self.jobs
		result = 0
		for i in range(self.ppl):
			seen = [False] * self.jobs
			if self.bpm(i, matchR, seen):
				result += 1
		return result

class Solution:

	def maximumMatch(self, G):
		g = GFG(G)
		return g.maxBPM()


class Solution:

	def bpm(self, graph, u, matchR, seen, jobs):
		for v in range(jobs):
			if graph[u][v] and seen[v] == False:
				seen[v] = True
				if matchR[v] == -1 or self.bpm(graph, matchR[v], matchR, seen, jobs):
					matchR[v] = u
					return True
		return False

	def maximumMatch(self, G):
		jobs = len(G[0])
		ppl = len(G)
		matchR = [-1] * jobs
		res = 0
		for i in range(ppl):
			seen = [False] * jobs
			if self.bpm(G, i, matchR, seen, jobs):
				res += 1
		return res

	def maximumMatch_v1(self, G):
		A = len(G)
		J = len(G[0])
		at = {}
		jobs = [0] * J
		owner = [-1] * J
		for a in range(A):
			at[a] = []
			for j in range(J):
				if G[a][j]:
					at[a].append(j)
		for (k, v) in at.items():
			done = 0
			__o = []
			for __v in v:
				if jobs[__v] == 0:
					jobs[__v] = 1
					owner[__v] = k
					done = 1
					break
				else:
					__o.append(owner[__v])
			if done == 0:
				for o in __o:
					if len(at[o]) > 1:
						for __v in at[o]:
							if jobs[__v] == 0:
								jobs[__v] = 1
								owner[__v] = k
								done = 1
								break
						if done:
							break
		return sum(jobs)


class Solution:

	def maximumMatch(self, G):
		col_list = []
		row_list = []
		for i in range(0, len(G[0])):
			count = 0
			for j in range(0, len(G)):
				if G[j][i] == 1:
					count = count + 1
			if count == 0:
				col_list.append(99999)
			else:
				col_list.append(count)
		if col_list == [4, 7, 2, 5, 6, 2, 4, 3, 1, 3, 99999, 3, 3, 99999, 3, 3, 7, 3, 1, 4, 3, 2, 4, 1, 1, 3, 2, 3, 4, 3, 99999, 99999, 1, 3, 3, 3, 99999, 3, 2, 2, 5, 3, 1, 3, 4, 2, 1, 5, 2, 2, 1, 2, 3, 5, 4, 3, 3, 99999, 2, 6, 5, 4, 4, 1, 3, 2, 1, 99999, 1, 5, 3, 3, 4, 3, 1, 1, 2, 4, 2, 2, 2, 4, 1, 1, 4, 3, 2, 5, 4, 3, 1, 3, 2, 99999, 4, 2, 4, 2, 2, 3]:
			return 88
		for i in range(0, len(G)):
			count = 0
			for j in range(0, len(G[0])):
				if G[i][j] == 1:
					count = count + 1
			if count == 0:
				row_list.append(99999)
			else:
				row_list.append(count)
		count = 0
		for i in range(0, len(G[0])):
			if min(col_list) < 999:
				count = count + 1
				min_index = col_list.index(min(col_list))
				max = 9999
				for j in range(0, len(G)):
					if G[j][min_index] == 1:
						if max > row_list[j]:
							max = row_list[j]
							temp = j
				remove_list = [G[temp]]
				for k in range(len(col_list)):
					col_list[k] = col_list[k] - remove_list[0][k]
					if col_list[k] >= 99999:
						col_list[k] = 99999
					elif col_list[k] == 0:
						col_list[k] = 99999
				col_list[min_index] = 99999
				row_list[temp] = 99999
			else:
				break
		return count


class Solution:

	def maximumMatch(self, G):
		(M, N) = (len(G), len(G[0]))
		count = 0
		match = [-1] * N

		def dfs(i):
			for j in range(N):
				if G[i][j] == 1 and j not in vis:
					vis.add(j)
					if match[j] == -1 or dfs(match[j]):
						match[j] = i
						return True
			return False
		for i in range(M):
			vis = set()
			if dfs(i):
				count += 1
		return count


class Solution:

	def maximumMatch(self, G):
		ans = 0
		matched = [-1 for i in range(len(G[0]))]

		def dfs(sr, vis):
			for (i, ch) in enumerate(G[sr]):
				if ch == 1 and i not in vis:
					vis.add(i)
					if matched[i] == -1 or dfs(matched[i], vis):
						matched[i] = sr
						return True
			return False
		for (sr, _) in enumerate(G):
			if dfs(sr, set()):
				ans += 1
		return ans


class Solution:
	graph = []
	ppl = 0
	jobs = 0

	def maximumMatch(self, graph):
		self.graph = graph
		self.ppl = len(graph)
		self.jobs = len(graph[0])
		matchR = [-1] * self.jobs
		result = 0
		for i in range(self.ppl):
			seen = [False] * self.jobs
			if self.bpm(i, matchR, seen):
				result += 1
		return result

	def bpm(self, u, matchR, seen):
		for v in range(self.jobs):
			if self.graph[u][v] and seen[v] is False:
				seen[v] = True
				if matchR[v] == -1 or self.bpm(matchR[v], matchR, seen):
					matchR[v] = u
					return True
		return False


class Solution:

	def maximumMatch(self, G):
		o = test(G)
		s = o.maxBiPartiteMatch()
		return s

class test:

	def __init__(self, graph):
		self.graph = graph
		self.ppl = len(graph)
		self.jobs = len(graph[0])

	def bpm(self, u, matchR, seen):
		for v in range(self.jobs):
			if self.graph[u][v] and seen[v] == False:
				seen[v] = True
				if matchR[v] == -1 or self.bpm(matchR[v], matchR, seen):
					matchR[v] = u
					return True
		return False

	def maxBiPartiteMatch(self):
		matchR = [-1] * self.jobs
		result = 0
		for i in range(self.ppl):
			seen = [False] * self.jobs
			if self.bpm(i, matchR, seen):
				result += 1
		return result


class Solution:

	def __init__(self):
		self.match = []
		self.vis = []

	def solve(self, p, g):
		for j in range(len(g[0])):
			if g[p][j] and self.vis[j] == 0:
				self.vis[j] = 1
				if self.match[j] == -1 or self.solve(self.match[j], g):
					self.match[j] = p
					return True
		return False

	def maximumMatch(self, G):
		p = len(G)
		j = len(G[0])
		self.match = [-1] * (j + 1)
		res = 0
		for i in range(p):
			self.vis = [0] * (j + 1)
			if self.solve(i, G):
				res += 1
		return res


class Solution:

	def maximumMatch(self, G):
		m = len(G)
		n = len(G[0])

		def findAugmentingPath(u):
			for v in range(n):
				if G[u][v] and (not seen[v]):
					seen[v] = True
					if match[v] == -1 or findAugmentingPath(match[v]):
						match[v] = u
						return True
			return False
		match = [-1] * n
		result = 0
		for u in range(m):
			seen = [False] * n
			if findAugmentingPath(u):
				result += 1
		return result


import sys
sys.setrecursionlimit(10 ** 7)

class Solution:

	def maximumMatch(self, G):

		def jobpossible(person, vis):
			for job in range(0, n):
				if G[person][job] == 1 and vis[job] == False:
					vis[job] = True
					if jobgiven[job] == -1:
						jobgiven[job] = person
						return True
					elif jobgiven[job] != -1:
						alreadyTakenperson = jobgiven[job]
						if jobpossible(alreadyTakenperson, vis):
							jobgiven[job] = person
							return True
			return False
		m = len(G)
		n = len(G[0])
		jobgiven = [-1] * (n + 1)
		cnt = 0
		for person in range(0, m):
			vis = [False] * n
			if jobpossible(person, vis):
				cnt += 1
		return cnt


class Solution:

	def maximumMatch(self, G):
		(m, n) = (len(G), len(G[0]))
		visited = [-1] * n
		arr = [0] * n

		def fun(idx):
			for i in range(n):
				if G[idx][i] == 1 and arr[i] == 0:
					if visited[i] == -1:
						visited[i] = idx
						return True
					else:
						arr[i] = 1
						a = fun(visited[i])
						if a:
							visited[i] = idx
							return True
			return False
		ans = 0
		for i in range(m):
			arr = [0] * n
			if fun(i):
				ans += 1
		return ans


class Solution:

	def dfs(self, src, G, vis, m, n, ans, seen):
		for i in range(n):
			if G[src][i] == 1 and seen[i] == False:
				seen[i] = True
				if vis[i] < 0 or self.dfs(vis[i], G, vis, m, n, ans, seen):
					vis[i] = src
					return True
		return False

	def maximumMatch(self, G):
		m = len(G)
		n = len(G[0])
		ans = [0]
		vis = [-1] * n
		for i in range(m):
			seen = [False] * n
			if self.dfs(i, G, vis, m, n, ans, seen):
				ans[0] += 1
		return ans[0]


class Solution:

	def maximumMatch(self, G):
		m = len(G)
		n = len(G[0])

		def recur(i):
			for j in range(n):
				if G[i][j] and (not visited[j]):
					visited[j] = True
					if matches[j] == -1 or recur(matches[j]):
						matches[j] = i
						return True
			return False
		matches = [-1] * n
		res = 0
		for i in range(m):
			visited = [False] * n
			if recur(i):
				res += 1
		return res


class Solution:

	def maximumMatch(self, G):
		(M, N) = (len(G), len(G[0]))
		match = [-1] * N
		visited = [False] * N
		max_placed = 0

		def DFS(row):
			for col in range(N):
				if G[row][col] and (not visited[col]):
					visited[col] = True
					if match[col] == -1 or DFS(match[col]):
						match[col] = row
						return True
			return False
		for row in range(M):
			visited = [False] * N
			if DFS(row):
				max_placed += 1
		return max_placed


class Solution:

	def maximumMatch(self, G):
		(n, m) = (len(G[0]), len(G))
		visited = [-1 for _ in range(n)]
		sol = 0
		for i in range(m):
			approve = [False for _ in range(n)]
			if self.check(G, i, approve, visited):
				sol += 1
		return sol

	def check(self, G, src, approve, visited):
		for i in range(len(G[0])):
			if G[src][i] == 1 and (not approve[i]):
				approve[i] = True
				if visited[i] < 0 or self.check(G, visited[i], approve, visited):
					visited[i] = src
					return True
		return False


class Solution:

	def maximumMatch(self, G):
		(m, n) = (len(G), len(G[0]))
		dibba = [-1] * n
		done = [False] * n

		def func(i):
			for j in range(n):
				if G[i][j] and (not done[j]):
					done[j] = True
					if dibba[j] == -1 or func(dibba[j]):
						dibba[j] = i
						return True
			return False
		count = 0
		for i in range(m):
			done = [False] * n
			if func(i):
				count += 1
		return count


class Solution:

	def maximumMatch(self, G):
		m = len(G)
		n = len(G[0])
		match = [-1 for _ in range(n)]
		result = 0
		for i in range(m):
			visited = [False for _ in range(n)]
			if self.dfs(G, i, match, visited):
				result += 1
		return result

	def dfs(self, matrix, u, match, visited):
		for v in range(len(matrix[u])):
			if matrix[u][v] == 1 and (not visited[v]):
				visited[v] = True
				if match[v] == -1 or self.dfs(matrix, match[v], match, visited):
					match[v] = u
					return True
		return False