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.
Note: the main logic is completely the same. Any help would be appreciated. Thanks in advance.
Auto comment: topic has been updated by NTTilted (previous revision, new revision, compare).
hi, from my personal view, i'd like to argue your Dfs function implementaion.
see wiki it mentions that "Also observe that the DFS does not visit the same vertex multiple times. This is thanks to the following lines: Dist[u] = ∞;return false;"
in your case, maybe you can add
distance_[node]=-1beforereturn false. your Kuhn version use used_ to do similar stuff.unfortunately i can't explain why the current version can pass library checker. And my version without-1 is just a few milliseconds longer than with-1
hope this helps.
Thanks a lot! I will test your version as soon as I come home. Upd: now it works! I still cannot make a counterexample to the previous version, but it definitely exists... Thank you again!