El problema es preguntarse si las aristas individuales en una versión dirigida del grafo dado deben tener una orientación fija para mantener la accesibilidad entre los pares de nodos dados.

Ciclos. Considere un ciclo en el grafo. Podemos dirigir todas las aristas para formar un ciclo dirigido en una o en la otra dirección. De esta manera, todos los nodos son accesibles entre sí dentro de un ciclo. Comprimamos el ciclo en un solo nodo y repitamos el proceso hasta que no queden más ciclos y nos quedemos con un bosque. Podríamos comenzar con cualquier ciclo en cualquier dirección, por lo tanto, la respuesta para todos las aristas comprimidas es B. Porque hay una ruta única entre un par de nodos (si son parte del mismo componente) estas aristas tendrán una orientación fija. Simplemente dirija las aristas a lo largo del camino desde el inicio a destino. Esto resuelve el problema, pero no con la suficiente eficacia, así resolvemos la primera subtarea.

Puentes. Después de comprimir los ciclos nos quedamos con un árbol. Las aristas de este árbol son los puentes(bridges) del grafo original, que podemos encontrar en tiempo lineal con el algoritmo de Tarjan. Esto resuelve la segunda subtarea.

Lowest common ancestor(LCA). La única fuente de ineficiencia proviene de dirigir las aristas. Pasar por todos los bordes en cada camino lleva demasiado tiempo y podríamos dirigir el mismo borde varias veces. ¿Podemos evitar esto?

Un enfoque consiste en procesar las rutas en un orden útil. Vamos a rootear el árbol en algún nodo y procesarlo en ~O (n \log{n})~ para responder las consultas de ancestros comunes más bajos en ~O (\log{n})~. Podemos dividir cada camino entre dos nodos en dos partes: una que sube por el árbol y la otra bajando, y luego resolver el problema de las rutas que van desde un nodo hacia la raíz. Procesaremos las rutas por sus antepasados ​​comunes más bajos(LCA) comenzando por los más cercanos a la raíz. Cuando estemos dirigiendo los bordes en un camino hacia la raíz, podríamos en algún momento alcanzar una arista ya dirigida y todas las aristas a partir de ahí ya estarán dirigidas en la misma dirección. Si existe una solución, esta dirección también será la correcta, de lo contrario tendríamos una contradicción.

También podemos resolverlo con tablas acumulativas sobre el árbol. Si hay un camino bajando de ~u~ a ~v~ sumamos 1 de ~u~ a ~v~ por medio de una tabla acumulativa, y para el camino subiendo restamos 1 en ese camino, después analizamos los nodos, si el resultado de la tabla acumulativa en ~u~ es positivo, hay que dirigir la arista de su él a su padre, si es negativo de su padre a él, y si es 0 se puede dirigir de cualquiera de las dos formas.