La Conferencia de Paz de la Federación (continuación)

Como ya sabemos, por haber resuelto el problema Y63099, la Federación de
Planetas Unidos organiza una importante conferencia de paz a la que
asistirán delegaciones de diferentes especies: Vulcanianos, Klingons,
Romulanos, Bajoranos, Ferengis, y otros. Por invitación de su comandante
B. Sisko, la conferencia tiene lugar en la estación Deep Space 9 en
órbita del planeta Bajor, que pronto se unirá a la Federación (pero aún
no lo ha hecho). Se han logrado bastantes progresos y algunos delegados
darán una rueda de prensa. Elegir a quienes van a participar en ella es
un tema delicado, porque hay delegados que odian a otros (muchas veces,
aunque no siempre, el odio es mutuo). No queremos tener en la mesa de la
rueda de prensa a dos delegados cuando uno de ellos odia al otro, pero
sí querríamos que hubiera el máximo posible de delegados.

El doctor Bashir ha visto en seguida todas las posibilidades pero, a
continuación, se ha ido a un congreso y no ha dejado ninguna copia de
sus anotaciones. Tendrás que ayudar a Sisko reconstruyéndolas. Qapla’!

Entrada

Un entero no negativo n que indica cuántos pares de nombres siguen, y n
pares de nombres que indican que la primera persona del par odia a la
segunda. El valor n aparece solo en una línea y, después, hay un par por
línea. Se garantiza que todo delegado odia a otro o bien es odiado por
algún otro: no hay nombres que no aparezcan en algún par.

Salida

El número más alto de delegados que pueden participar en la rueda de
prensa sin que ninguno de los participantes odie a ningún otro, seguido,
a partir de la línea siguente, de todas las maneras de alcanzar ese
tamaño, con una solución por línea.

Pista

Hay que aplicar un esquema de backtracking.

Observación

El enunciado no descarta el valor n = 0. En ese caso, hay exactamente
una solución (¡vacía!).

Información sobre el corrector

Podéis escribir en cualquier orden tanto las soluciones como los
elementos dentro de cada solución.

Información del problema

Autoría: Unknown
Traducción: José Luis Balcázar

Generación: 2026-06-05T06:25:44.046Z

© Jutge.org, 2006–2026.
https://jutge.org
