Course Schedule
Hay numCourses cursos, numerados del 0 al numCourses-1. Cada par [a, b] en prerequisites significa que tienes que terminar el curso b antes de empezar el curso a. Devuelve true si algún orden te permite terminar todos los cursos, y false si ninguno lo permite.
Función
- numCoursesinteger
- el número de cursos
- prerequisitesinteger-2d-array
- los pares [a, b], cada uno indica que el curso b va antes que el curso a
- Devuelveboolean
- verdadero si se pueden terminar todos los cursos, falso en caso contrario
Restricciones
1 ≤ numCourses ≤ 1051 ≤ prerequisites.length ≤ 5000- Cada par
[a, b]cumple0 ≤ a, b < numCourses. - No hay ningún par que aparezca dos veces.
- Un par puede nombrar dos veces el mismo curso,
[a, a]. Ese curso se necesita a sí mismo primero, así que nunca se puede cursar.
Ejemplos
- Entrada
- numCourses = 4prerequisites = [[1, 0], [2, 1], [3, 1]]
- Salida
- true
- Explicación
- El curso 0 no tiene requisitos previos, así que lo tomas primero. Eso libera el curso 1, que libera los cursos 2 y 3, así que el orden 0, 1, 2, 3 funciona.
- Entrada
- numCourses = 3prerequisites = [[0, 2], [2, 1], [1, 0]]
- Salida
- false
- Explicación
- El curso 0 espera al 2, el 2 espera al 1 y el 1 espera al 0. Los tres se esperan entre sí en un ciclo, así que ninguno puede ir primero.
Para ir más allá
Cualquier número de cursos cabe en un trimestre, siempre que los requisitos previos de cada curso se hayan completado en trimestres anteriores. ¿Cuál es el menor número de trimestres que permite cubrir todos los cursos?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Dibuja cada curso como un punto y cada par
[a, b]como una flecha debaa. ¿Qué forma en ese dibujo haría imposible terminar?Un ciclo de flechas. Cada curso de un ciclo espera a otro curso del mismo ciclo, así que ninguno puede ir primero. La pregunta es si el grafo tiene un ciclo.
Cuenta cuántos prerrequisitos le faltan a cada curso. Empieza una cola con los cursos cuyo recuento es 0 y, cada vez que saques uno, reduce el recuento de todos los cursos que dependen de él. Si menos de
numCoursescursos llegan a la cola, hay un ciclo.
Solución
Dibuja una flecha b → a para cada par [a, b]. Cada curso se puede terminar exactamente cuando este grafo, con V = numCourses nodos y E = prerequisites.length flechas, no tiene ciclos. El algoritmo de Kahn lo comprueba como lo planifica un estudiante: sigue tomando un curso cuyos prerrequisitos estén completados y comprueba si se toman todos los cursos.
Toma todos los cursos gratuitos, ronda tras ronda
Correcto, pero no termina con las pruebas más grandes
Intuición
En cada ronda, toma todos los cursos que aún no hayas tomado y cuyos prerrequisitos ya hayas completado. Detente cuando en una ronda no tomes ningún curso y responde true si completaste todos los cursos. En una ronda no se toma ningún curso solo cuando cada curso restante está esperando a otro curso restante, lo que forma un ciclo.
En cada ronda se vuelven a leer todos los pares y todos los cursos, aunque quizá solo se tome un curso. Una cadena de 5,001 cursos entre 100,000 requiere más de 5,000 rondas: unos 5 × 10^8 comprobaciones.
Algoritmo
- Marca cada curso como no cursado.
- Marca un curso como bloqueado si algún par le asigna un prerrequisito que no está cursado.
- Cursa todos los cursos que no estén cursados ni bloqueados.
- Si en la ronda no se cursó ningún curso, detente; de lo contrario, vuelve al paso 2.
- Devuelve true si todos los cursos están cursados.
def canFinish(numCourses, prerequisites):
taken = [False] * numCourses
count = 0
while True:
# A course is blocked while one of its prerequisites is not taken.
blocked = [False] * numCourses
for course, before in prerequisites:
if not taken[before]:
blocked[course] = True
# Take every course that is free this round.
progress = False
for c in range(numCourses):
if not taken[c] and not blocked[c]:
taken[c] = True
count += 1
progress = True
if not progress:
break
return count == numCoursesBúsqueda en profundidad con tres estados
Intuición
La búsqueda en profundidad encuentra un ciclo siguiendo la ruta que recorre. Asigna a cada curso uno de tres estados: no visitado, en la ruta, terminado. Sigue las flechas de un curso a los cursos que dependen de él. Marca un curso como en la ruta al entrar en él y como terminado cuando se hayan explorado todas sus flechas.
Una flecha hacia un curso que está en la ruta cierra un ciclo: devuelve false. Una flecha hacia un curso terminado es segura, porque se comprobó todo lo que se puede alcanzar desde él y no contiene ciclos, así que llegar dos veces a un curso no forma por sí solo un ciclo. Se entra en cada curso una vez y se sigue cada flecha una vez: O(V + E).
Algoritmo
- Construye, para cada curso, la lista de cursos que esperan por él.
- Para cada curso que no se haya visitado, márcalo en el camino y ponlo en una pila.
- Mira la cima de la pila. Si no le queda ninguna flecha, márcalo como terminado y sácalo de la pila; de lo contrario, sigue su siguiente flecha.
- Si la flecha lleva a un curso que está en el camino, devuelve false. Si lleva a un curso que no se ha visitado, marca ese curso en el camino y ponlo en la pila.
- Cuando todos los cursos estén terminados, devuelve true.
def canFinish(numCourses, prerequisites):
unlocks = [[] for _ in range(numCourses)]
for course, before in prerequisites:
unlocks[before].append(course)
# 0 = not visited, 1 = on the current path, 2 = done, no cycle below it
state = [0] * numCourses
# next_edge[c] counts the edges out of c the search has already followed.
next_edge = [0] * numCourses
for start in range(numCourses):
if state[start] != 0:
continue
# A stack of our own instead of recursion: a chain of 5,000
# courses would go 5,000 calls deep.
state[start] = 1
stack = [start]
while stack:
course = stack[-1]
if next_edge[course] == len(unlocks[course]):
state[course] = 2
stack.pop()
continue
nxt = unlocks[course][next_edge[course]]
next_edge[course] += 1
if state[nxt] == 1:
return False # an edge back to the current path closes a cycle
if state[nxt] == 0:
state[nxt] = 1
stack.append(nxt)
return TrueAlgoritmo de Kahn
Intuición
Un curso pasa a estar disponible en un momento: cuando se cursa su último prerrequisito. Así que lleva la cuenta del grado de entrada de cada curso —el número de prerrequisitos que aún le faltan— y comienza con una cola que contenga todos los cursos cuyo contador sea 0. Al cursar un curso, se reduce en uno el contador de cada curso que depende de él, y los cursos cuyo contador llega a 0 se añaden a la cola. En el primer ejemplo, los contadores empiezan en 0, 1, 1, 1: cursar 0 libera 1, y cursar 1 libera 2 y 3. Cada curso entra en la cola una vez y cada par reduce un contador una vez: O(V + E).
Si la cola se vacía mientras el curso a aún no se ha cursado, su contador es mayor que 0, así que algún prerrequisito de a tampoco se ha cursado, y así sucesivamente. Ese recorrido necesariamente vuelve a visitar un curso: hay un ciclo. A la inversa, cada curso de un ciclo depende de otro curso del mismo ciclo, así que ninguno puede ir primero. El orden en que los cursos salen de la cola es una planificación válida.
Algoritmo
- Para cada par [a, b], agrega a a la lista de cursos que esperan a b y suma 1 al grado de entrada de a.
- Coloca en una cola todos los cursos con grado de entrada 0.
- Saca un curso de la cola y cuéntalo. Reduce el grado de entrada de cada curso que lo espera y agrega a la cola cada uno que llegue a 0.
- Cuando la cola esté vacía, devuelve si el recuento es igual a
numCourses.
from collections import deque
def canFinish(numCourses, prerequisites):
# unlocks[b] lists the courses that wait for b.
# indegree[a] counts the prerequisites of a that are not taken yet.
unlocks = [[] for _ in range(numCourses)]
indegree = [0] * numCourses
for course, before in prerequisites:
unlocks[before].append(course)
indegree[course] += 1
# Every course with no prerequisites can be taken right away.
queue = deque(c for c in range(numCourses) if indegree[c] == 0)
taken = 0
while queue:
course = queue.popleft()
taken += 1
for nxt in unlocks[course]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt)
# A course on a cycle never gets down to 0, so it is never taken.
return taken == numCourses
Errores comunes y casos límite
- Confundir la dirección.
[a, b]significa que b va primero: la flecha va de b a a, y el grado de entrada de a aumenta. - Olvidar los cursos que no aparecen en ningún par. Con
numCourses = 5y el único par[4, 3], los cursos 0, 1 y 2 también deben empezar en la cola. - Usar dos estados en lugar de tres en la búsqueda en profundidad. En el diamante 0 → 1, 0 → 2, 1 → 3, 2 → 3, se llega al curso 3 dos veces y parece un ciclo si solo registras los elementos «vistos».
- Recurrir en una cadena de 5,000 cursos: 5,000 llamadas de profundidad, por encima del límite predeterminado de Python de 1,000.
- Devolver true cuando la cola se vacía sin comprobar que se hayan cursado
numCoursescursos. El segundo ejemplo devolvería true.
Preguntas frecuentes3
¿Cuál es la complejidad temporal del problema del horario de cursos?
O(V + E), donde V es el número de cursos y E el número de pares, ya sea con el algoritmo de Kahn o con la búsqueda en profundidad. Cada par se lee una vez y cada curso se procesa una vez. Las listas y los recuentos ocupan O(V + E) espacio.
¿Deberías usar BFS o DFS para la planificación de cursos?
Ambos se ejecutan en O(V + E). El algoritmo de Kahn, la versión de búsqueda en anchura, no tiene que preocuparse por la profundidad de la recursión y te da un orden válido de los cursos. La búsqueda en profundidad con tres estados es la opción natural cuando también tienes que informar del ciclo, porque los cursos en su pila lo forman.
¿Qué es una ordenación topológica?
Un orden de los nodos de un grafo dirigido en el que cada flecha apunta hacia adelante; aquí, un orden en el que cada requisito previo aparece antes que el curso que lo necesita. Existe exactamente cuando el grafo no tiene ciclos, y el orden en que el algoritmo de Kahn toma los cursos es uno de ellos. Course Schedule pregunta si existe tal orden.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def canFinish(numCourses, prerequisites):
# Escribe el código aquíPrueba #1
Prueba #2
Argumentos
numCourses = 4 prerequisites = [[1, 0], [2, 1], [3, 1]]
Salida Esperada
true