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.
Problem 1: SPOJ
Problem 2: CodeChef
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)