Problem with Hopcroft-Karp algorithm
Difference between en1 and en2, changed 7 character(s)
Hello, Codeforces!↵
Recently I have been reading about relationship between flows and matchings and I've decided to solve a couple of problems related to this topic. So, before starting the problems, I implemented Hopcroft-Karp algorithm for matching in bipartite graphs and tested it here: [Link](https://judge.yosupo.jp/submission/123334).↵

While solving the "Dominoes" problem (unfortunately, I haven't found this problem somewhere except 
of eolymp: [this](https://www.eolymp.com/ru/problems/1738) or [this](https://www.eolymp.com/ru/problems/2086), they are completely same), it turned out, that my implementation actually TLEs on a certain testcases. Since constraints are small enough, I tried to find matching with Dinic and then with Kuhn, and these submissions got AC as they should.↵

So, I felt in doubt about correctness of my Hopcroft-Karp implementation — since it TLEs, there must be an infinite cycle. I've spent hours to prove for myself that my implementation is actually correct, and seems that it is — I'm unable to find the mistake. I have no clue what is wrong with it, and I don't have any testcase which make Hopcroft-Karp to work infinitely. ↵

[Kuhn AC](https://pastebin.com/CQNitEkW)↵

[Dinic AC](https://pastebin.com/WX80AFEN)↵

[Hopcroft-Karp TLE](https://pastebin.com/X1wa0Zx5)↵

Note: the main logic is completely the same.↵
Any help would be appreciated. Thanks in advance. 

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English NTTilted 2023-01-29 12:41:18 7 (published)
en1 English NTTilted 2023-01-29 12:40:39 1454 Initial revision (saved to drafts)