Bipartite Matching via Max Flow

Problem

Compute the maximum bipartite matching size by reducing it to an s-t max flow.

Wire a unit-capacity network: source to every left node, left node to its right neighbors, every right node to the sink, then run Ford-Fulkerson and return the flow value. adj[i] lists the right nodes adjacent to left node i. L and R give the side sizes.

Hint

Every unit of flow picks one matched pair, so the flow value equals the matching size.

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

Starter codePython

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

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