← Volver a los ejercicios

Pick up sticks: los tres estados y los ciclos

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ó?

1. Decida en cada arista

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.

2. El código, paso a paso

Camino actual:
orden:
Paso 0 de 0

3. Con dos estados

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.

4. Para llevarse

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?