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.
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.
