Easy and Clean Implementation of Hopcroft-Karp-Karzanov Algorithm for Maximum Bipartite Matching

Revision en1, by pks18, 2021-08-13 11:26:19

While trying the problem Tree Matching, I figured out that onw way to solve the problem could be to use network flow by adding a source and sink after splitting the tree into two partite. Otherwise, another way could be to use Hopcroft-Karp Algorithm to find the maximum matching.

There is no article written on this topic on CP Algorithms website. And on other webisites, I didn't find a implementation as clear and general as they are on CP Algorithms.

It would be great if some clean and documented implementation of this code could be shared (may or may not be a blogpost on Codeforces).

Thanks in advance!

Tags #bipartite, biparite matching, hopcroft-karp, tree

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English pks18 2021-08-13 11:26:19 786 Initial revision (published)