PreviousNext
Coding/Graphs and trees

Maximum applicant job assignment

Write codeHard40 min

Your task

There are n applicants and m jobs. You are given an adjacency list where allowed[i] is the list of job indices (0..m-1) applicant i can do. Each applicant can be assigned at most one job and each job to at most one applicant. Return the maximum number of applicants that can be assigned a job (the size of a maximum bipartite matching).

Examples

max_bipartite_matching(n: int, m: int, allowed: list[list[int]]) -> int
Example 1
Inputmax_bipartite_matching(3, 3, [[0, 1], [0], [0, 2]])
Output3