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.
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.
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.
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.
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.
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.
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.