← Volver a los ejercicios

De la entrada al grafo

Ordering Tasks con otra instancia. Lo que decide el problema no es el algoritmo, que ya está escrito, sino qué se lee como vértice y en qué sentido va cada flecha; y entre la entrada y la lista de adyacencia hay una resta que se olvida seguido.

1. La entrada

6 6
1 4
4 2
1 3
5 4
6 1
3 2
0 0

Seis tareas numeradas de 1 a 6 y seis precedencias: cada línea i j dice que la tarea i debe ejecutarse antes que la j. La instancia termina con 0 0.

Entrada: n, m y las m parejas.  Salida: una línea con las seis tareas en un orden de ejecución que respete las seis precedencias.

A mano, sobre esta entrada: la tarea 1 espera a la 6; la 4 espera a la 1 y a la 5; la 2 espera a la 4 y a la 3; la 3 espera a la 1. Las únicas que no esperan a nadie son la 5 y la 6.

2. ¿Qué lista de adyacencia construye la lectura?

3. Ejecute la lectura

Pareja: –
G: –
Paso 0 de 0
El dibujo numera las tareas desde 1, como el enunciado; la lista guarda índices desde 0.

4. ¿Qué imprime el programa?

5. Para llevarse

Sin solución aquí. Agregue a esta instancia una séptima precedencia que la deje sin ningún orden válido, y diga qué imprimiría el programa de la clase con esa entrada. Después, ¿qué habría que cambiarle para que en ese caso imprima una palabra en vez de una lista corta?