← Volver a los ejercicios

Tres fallas en cortes y en Tarjan

Tres versiones con una línea cambiada. Ninguna revienta al correr: las tres devuelven una respuesta con aspecto de respuesta, y hay que compararla con la de la versión correcta para darse cuenta. En cada una, se corre sobre un grafo pequeño, se miran las dos salidas y los valores d y low, y después se señala la línea. La explicación aparece al acertar.

4. Para llevarse

Sin solución aquí. Dibuje un grafo no dirigido donde la primera versión, la que no distingue al padre, devuelva por casualidad la lista correcta de puentes, y diga qué tiene ese grafo de particular. Después conteste: en la segunda versión, ¿hay grafos en los que el ≥ en la línea del puente no cambia nada? Y en la tercera, ¿qué forma tiene un grafo dirigido donde d[v] != 0 y en_pila[v] dan siempre el mismo resultado?