← Volver a los ejercicios

Las calles de una ciudad, UVa 610

Hay que convertir en una vía tantas calles como se pueda, de modo que desde cada intersección se siga pudiendo llegar a todas las demás. La profundidad orienta las aristas de árbol del padre al hijo y las de retroceso del descendiente al ancestro; la calle que no se puede convertir se emite en los dos sentidos. Aquí se ejecuta la orientación y se comprueba cuáles calles quedaron de doble vía.

1. La ciudad y la predicción

Ciudad:

Entrada: las intersecciones de 1 a n y las calles de doble vía, a lo sumo una por cada par; con todas de doble vía se puede ir de cualquier intersección a cualquier otra.  Salida: cada calle como una pareja orientada; la que no se puede convertir, dos veces.

¿Cuántas líneas tiene la salida?

2. Ejecute la orientación

Recorrido:
llamadas: vacía
salida (0 líneas): vacía
Paso 0 de 0
→ calle ya orientada, una vía → calle de doble vía sobre cada intersección, d/low

La versión de pila explícita es la que se envía al juez: con mil intersecciones en línea la rama tiene profundidad mil y la recursiva se cae contra el límite de Python.

3. Calle por calle

CalleExtremosSentidos emitidosQueda¿Es puente?

4. ¿Se llega a todas?

Elija una intersección y vea a cuáles se llega por la ciudad ya orientada. Con la orientación completa hay que llegar a todas desde cualquiera: eso es lo que pide el enunciado.

5. Para llevarse

Sin solución aquí. En la primera ciudad, oriente a mano arrancando en la 5 en vez de en la 1: la lista de parejas cambia, la calle de doble vía no. Explique por qué, con el teorema que dice que el conjunto de puentes no depende de dónde arranque la profundidad. Después, en la segunda ciudad, borre la comparación d[v] < d[u] del elif y diga cuántas líneas tendría la salida y por qué el juez la rechaza aunque la orientación sea fuertemente conexa. Y por último, en la tercera ciudad, agregue una intersección nueva colgada de la 4 por una sola calle: ¿cuántas calles quedan sin convertir?