Problem with Hopcroft-Karp algorithm

Revision en2, by NTTilted, 2023-01-29 12:41:18

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.

While solving the "Dominoes" problem (unfortunately, I haven't found this problem somewhere except of eolymp: this or this, 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

Dinic AC

Hopcroft-Karp TLE

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

Tags flows, matchings

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)