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

Правка en1, от 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!

Теги #bipartite, biparite matching, hopcroft-karp, tree

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский pks18 2021-08-13 11:26:19 786 Initial revision (published)