Maximum Bipartite Matching Size

Problem

Compute the size of a maximum matching in a bipartite graph with L left and R right nodes.

adj[i] lists the right nodes adjacent to left node i. Use Kuhn's algorithm: try to augment from each left node in order, rerouting existing matches when needed. Return the number of matched pairs.

Hint

Kuhn runs one DFS per left node; each success increases the matching by one.

Test cases

case 1

in: [3,3,[[0,1],[0],[1]]]

expected: 2

case 2

in: [2,2,[[0,1],[0,1]]]

expected: 2

case 3

in: [3,3,[[],[],[]]]

expected: 0

case 4

in: [4,4,[[0],[0],[2,3],[2]]]

expected: 3

case 5

in: [3,3,[[0,1],[1,2],[2]]]

expected: 3

Starter codePython

def max_bipartite_matching(L, R, adj):
    # Your code here
    pass

5 test cases · run your code against them in the editor