Hopcroft-Karp Phase Count

Problem

Count the BFS phases Hopcroft-Karp needs to build a maximum bipartite matching.

A phase BFS-layers unmatched left nodes and notices when a free right node is reachable; the following DFS scan augments along the layered graph. adj[i] lists right-side neighbors of left node i. Return [phases, matching_size].

Hint

Every phase strictly increases the length of the shortest augmenting path.

Test cases

case 1

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

expected: [1,2]

case 2

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

expected: [1,2]

case 3

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

expected: [0,0]

case 4

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

expected: [2,3]

case 5

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

expected: [1,4]

Starter codePython

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

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