I am trying to solve 1818D - Fish Graph with the following idea.
- For each node V whose degree is >= 4, do BFS starting from V to find the shortest cycle that includes V.
- If such a cycle exists, get all the nodes in this cycle, then check if we can add 2 more extra edges from V to other 2 nodes that are not in this cycle.
My submission (with some comments) is : 204063133. However I am getting WA on test case 2: wrong answer edge (4, 8) was used twice (test case 137).
I am sure my logic is incorrect somewhere but couldn't figure it out. Any help is appreciated.
8 8 8 4 3 4 7 4 8 2 6 8 3 7 5 1 8 5 This is the 137 case. I think you are not actually finding the shortest cycle or maybe you are doing something wrong while backtracking(adding edges included in special graph) . Overall your logic is correct, we do need to find the shortest cycle from a particular node.
It turns out that I made exactly the same mistake mentioned by wakaranai, which is demonstrated by the test case you provided. Thank you!
PS: how did you find out the test case, out of curiosity?
For T<=3 run your normal code but when T>3 print the TC when TC==137. https://codeforces.net/contest/1818/submission/204068118
I faced the exact same issue, with the exact same verdict.
Turns out, I was not considering the fact that if you run a bfs from a starting node and find a cycle, the starting node might not be part of that exact cycle (Imagine a bamboo connected to a cycle). To overcome this, simply check if a cycle can be formed from paths that start at different adjacent nodes of the starting node, and ignore all other cycles.
Yeah, this is exactly the mistake I made :) After 15 attempts, I finally got it right, I learned something new today! Thank you!
Quick note: You can easily get the shortest cycle by using a parent array and DFS. When you find the starting node while running DFS, just simply store a reference to the last node you reached and then return.
This always work because if you first find the longest cycle, you'd return and then the DFS would find the next shortest one and update that reference. But if you find the shortest one first, you'll again return and the DFS would end. check my submission for more detail: 203943422
Thank you for sharing :)
I haven't actually ran your code so apologies if you thought of this but I'm basing this off of your algorithm.
A regular bfs traversal doesn't work cuz your cycle might include vertices that you should've used for the two extra vertices instead.
Yes, you are right, thanks!