← Volver a los ejercicios

El recorrido que sube de influencia

Un mapa de planetas con rutas en los dos sentidos, un valor de influencia en cada planeta y uno de arranque. Dentro de un grupo que ningún puente separa se anda libre. El puente se cruza solo hacia un grupo de más influencia, y por eso el recorrido nunca se devuelve. Se piden los planetas alcanzados, ordenados por la influencia de su grupo, después por la propia y al final por número.

1. El mapa y la predicción

Mapa:

Entrada: los planetas de 1 a n, su influencia, las rutas como parejas sin dirección y el planeta de arranque.  Salida: los planetas alcanzados, en una línea.

sobre cada planeta, su influencia ○ planeta de arranque ┅ puente
¿Cuántos planetas alcanza el recorrido?

2. Los puentes

Clasifique cada ruta. Es puente cuando al quitarla sus dos extremos quedan sin camino entre ellos, y el recorrido en profundidad lo detecta con low[w] > vis[v]: nada del subárbol de w vuelve a v ni más arriba. El número sobre cada ruta es su identificador en la lista.

3. La influencia de cada grupo

Sin los puentes, el mapa queda repartido en grupos, cada uno conexo por las rutas que quedan. Escoja la influencia total de cada grupo: la suma de la influencia de sus planetas.

4. Puente por puente

La condición es influencia[grupo de u] < influencia[grupo de w], con desigualdad estricta. Los puentes van en el orden en que el recorrido se los encuentra: uno queda fuera de alcance cuando el camino hacia él pasa por otro que no se cruzó.

la cruza: la influencia sube y el recorrido pasa al otro lado.  la mira y no la cruza: el recorrido llega a uno de sus extremos y la condición falla.  no llega a mirarla: ninguno de sus dos extremos se alcanza.

5. La lista en orden

Escoja los planetas alcanzados separados por espacios, ordenados por influencia del grupo, después por influencia propia y al final por número. Las tres claves se comparan en ese orden y la siguiente solo entra a decidir cuando la anterior empata.

6. Para llevarse

Sin solución aquí. En el mapa de diez planetas, el planeta más rico de todos no se alcanza. Diga qué puente lo deja afuera, por qué el empate de influencias no basta para cruzarlo y cuánta influencia le falta al grupo intermedio para que entre; después, qué cambiaría con la comparación escrita ≤. En el de nueve, cambie el arranque al planeta 5 y diga cuántos alcanza, y pruebe también desde el 8: desde ahí llega a más, y conviene explicar por qué. En el de once el recorrido cruza un puente y rechaza dos; de esos dos, uno se cruzaría arrancando en el planeta 2 y el otro no, y hay que decir cuál es cuál. Y por último: construya dos mapas con los mismos cuatro grupos y los mismos tres puentes, uno donde el recorrido alcance todos los planetas y otro donde no salga del grupo del arranque.