UVa Online Judge – 12363 – Hedge Mazes

El link del problema es el siguiente:
12363 – Hedge Mazes

El problema es de Grafos.
En el problema, nos dan la descripción de un grafo, que son las conexiones entre sus nodos y un numero Q de consultas. Cada consulta esta compuesta de 2 números u,v que representan un nodo origen y un nodo destino y para cada una de las consultas, hay que responder de manera eficiente si solo existe un camino entre esos 2 nodos.
Si es que llega a existir un solo camino entre esos nodos, imprimimos una Y, en caso contrario, imprimimos una N.

Cuando digo de manera eficiente, me refiero a que las consultas se deben de hacer lo mas rápido posible.

La solución consiste en hacer uso de los puentes del grafo.
Un puente es una arista en el grafo que si es removida, el grafo se desconecta.
Si nos ponemos a pensar en este hecho, eso quiere decir que al pasar por el puente, solo existe ese camino único para ir de un nodo A a un nodo B.

Por lo tanto, tenemos que si dos nodos están conectados solamente por puentes, quiere decir que la ruta es única.
Así que la solución, es, una vez generados los puentes, podemos usar conjuntos disjuntos para obtener cuales elementos están en el mismo conjunto, y si están en el mismo conjunto, es que existe solo 1 camino entre ellos.

Código en C++