This repository has been archived by the owner on Oct 29, 2020. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 180
/
MBM.py
52 lines (41 loc) · 1.47 KB
/
MBM.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
# Author=====>>>Nipun Garg<<<=====
# Problem Statement - Given number of jobs and number of applicants
# And for each applicant given that wether each applicant is
# eligible to get the job or not in the form of matrix
# Return 1 if a person can get the job
def dfs(graph, applicant, visited, result,nApplicants,nJobs):
for i in range(0,nJobs):
if(graph[applicant][i]==1 and (not visited[i])):
visited[i]=1
if( result[i]<0 or dfs(graph, result[i], visited, result, nApplicants, nJobs)):
result[i]=applicant
return 1
return 0
#Return maximum people that can get the job
def bipartite(graph,nApplicants,nJobs):
result = []
for i in range(0,nJobs):
result.append(-1)
retval=0
for i in range(nApplicants):
visited = []
for j in range(nApplicants):
visited.append(0)
if(dfs(graph, i, visited, result, nApplicants, nJobs)):
retval+=1
return retval
#Main function
if __name__ == '__main__':
# Total number of applicant and total number of jobs
nApplicants = input("Enter the number of applicants : ")
nJobs = input("Enter the number of jobs : ")
graph = []
#Taking input if a user can have a job then its value for job is 1
for i in range(nApplicants):
print("Enter the status(1/0) for applicant - "+str(i+1)+" for "+str(nJobs)+" Jobs!")
temp=[]
for j in range(nJobs):
temp.append(input("For job - "+str(j+1)+" : "))
graph.append(temp)
# print(graph)
print("Maximum applicants that can have job is : "+str(bipartite(graph, nApplicants, nJobs)))