El problema de la sesión, UVa 11686. Un par a b dice que el palito a está
encima del b, y se pide un orden de recogida o IMPOSSIBLE si los palitos se cierran en
un ciclo. La pregunta del recorrido en profundidad es la misma en cada arista: ¿el nodo al que llega está en el
camino actual, o ya terminó?
El recorrido arranca desde todo nodo sin visitar, en orden, que es lo que hace main
con su ciclo sobre los palitos. En el juez los palitos van de 1 a n; el diamante arranca en 0.
Quien solo lleva visitado no distingue entre un nodo del camino actual y uno
que ya terminó, así que toda arista hacia un nodo visto le parece un ciclo. En rojo, los grafos donde esa versión
responde mal.
Sin solución aquí. Cuando un nodo termina, todo lo que sale de él ya terminó: explique por qué de ahí sale que el orden de terminación al revés respeta todas las aristas. Después piense en una cadena de un millón de palitos: ¿cuántas llamadas abiertas tiene la recursión al llegar al último, y qué guarda la versión con pila en lugar de cada una?