This is going to be a long post where the aim is to find the bug in one of the two implementations (or possibly I have already found it). So you can stop reading the moment you find me wrong and correct me.
I was reading the online bridge searching algorithm from here. What I found strange is that in the
merge_path() function, when we are finding the path from b to LCA(a,b), we are pushing b to the path(instead of the 2-edge-connected representative of b like we did for a. We are doing this because we are compressing the nodes to a single 2-edge-connected component).
What this may cause:
Suppose in the following graph, the next edge we want to add is (6,16). Now, suppose the 2-edge-connected representative of 6 isn’t 6 (let’s assume it is 2). So when we will be traversing from 16 to 2 (since 2 is the representative, it is the LCA too instead of 6), we will add 4 nodes in the path (16, 13, 12 and 6) and hence, will be decreasing the number of bridges by 4 but there were only 3 bridges before adding this edge which are not bridge anymore. Note that it is possible that the parent of 12 was 6 before adding this edge, and not 2.
After finding this possible bug in the implementation of the tutorial, I found two problems which are straightforward implementation of online bridge searching. Note that both the problems are exactly same.
Let’s look at the submissions of 2nd problem.
Wrong Answer on CodeChef : In this solution, the issue I’ve discussed above is taken care of but it gives WA on CodeChef. Strangely, when I submitted the same solution to SPOJ, it got accepted.
Accepted on CodeChef : This is the same implementation of the cp-algorithm tutorial, link of which I have posted above and it has been accepted. Once again, when I submitted this code on SPOJ, it was rejected.
I also asked the setter of the CodeChef problem for the test cases and according to his outputs, I can confirm that he has used the implementation of cp-algorithms. I am not sure if I can post the test cases publicly here, so I will prefer not to share it here but if anybody wants, I can email the test data.
So I wanted to ask if there is anything I am missing in concluding the fact that the implementation on cp-algorithm is wrong. What raises my doubt is that the author of that implementation has used different approach for jumping to the parent of b than jumping to parent of a for finding LCA(a,b) (even if it’s very minute, why would anybody do so? This raises doubt specially when this difference actually causes a problem)