Un país tiene ciudades y carreteras de una sola vía. La capital tiene que ser alcanzable desde todas las demás, y se piden las candidatas en orden creciente. Son los vértices del componente fuertemente conexo sumidero de la condensación: el componente del que no sale ninguna carretera hacia otro. Con dos sumideros no hay capital. Las ciudades de uno no se alcanzan desde las del otro, ni al revés.
Entrada: las ciudades de 1 a n y las
carreteras como parejas u v, que se recorren solo de
u a v. Salida: cuántas candidatas hay
y la lista en orden creciente; si no hay ninguna, un 0 solo.
Para cada ciudad, escoja el número menor de su componente. Dos ciudades van juntas cuando hay camino de la primera a la segunda y de la segunda a la primera; una sola dirección no alcanza. Una ciudad sin nadie con quien ir y venir queda sola y se representa a sí misma.
Cada componente se vuelve un nodo y las carreteras entre componentes distintos, las aristas. Lo que queda no tiene ciclos: si hubiera uno, los componentes del ciclo serían uno solo. Diga, componente por componente, si de él sale alguna carretera hacia otro.
Escoja la lista de candidatas en orden creciente,
separadas por espacios, o un 0 si no hay ninguna.
Sin componentes ni condensación: se elige una ciudad y se recorren las carreteras al revés para ver desde cuántas se llega a ella. Las que cumplen con todas son las mismas de la lista.
Sin solución aquí. En el país de siete ciudades, agregue una sola carretera que haga aparecer una capital y diga cuántas candidatas quedan. Después agregue otra distinta que devuelva la respuesta a cero. En el de ocho, quite la carretera que entra al par del final y cuente los sumideros que quedan. Y por último: construya un país donde todas las ciudades sean candidatas, y otro donde haya una sola candidata pero tres componentes; diga en cada caso cómo se ve la condensación.