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.
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.
salida (0 líneas): vacíad/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.
| Calle | Extremos | Sentidos emitidos | Queda | ¿Es puente? |
|---|
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.
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?