Hedge Mazes - ICPC Latin America

Now I solved problem Hedge Mazes, the statement is available here.

I will just give the idea of the solution. The problem basically requires that it should be answered for each query whether there is a single simple path that connects the given vertices or if there is more than one simple path.

So basically it is asked whether there is a loop in the path between the vertices. Well, the condition for there being no loops is that the whole path should be composed only of bridges. If an edge (vi, vj) of the path isn't a bridge then there is another way from vi to vj and so there is no longer only one path from vi to vj.

So now the only thing we need to do is to check the graph for bridges and later check the connectivity of the graph composed only by them. If two vertices are in the same component composed only of bridges then there is only a single path between them.

The code is available here.