← Volver a los ejercicios

Las candidatas a capital

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.

1. El país y la predicción

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

las carreteras entre dos ciudades del mismo componente se colorean al agrupar
¿Cuántas ciudades pueden ser capital?

2. Marque los componentes fuertemente conexos

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.

3. Contraiga y busque el sumidero

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.

○ componente sin carreteras de salida bajo cada nodo, cuántas carreteras salen hacia otros

4. La salida que pide el juez

Escoja la lista de candidatas en orden creciente, separadas por espacios, o un 0 si no hay ninguna.

5. Compruebe por la definición

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.

6. Para llevarse

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.