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