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 poder empezar el curso a. Devuelve true si hay un orden en el que puedes terminar todos los cursos, y false si no lo hay.
Función
- numCoursesinteger
- el número de cursos
- prerequisitesinteger-2d-array
- los pares [a, b], cada uno de los cuales significa que el curso b va antes que el curso a
- Devuelveboolean
- true si se pueden terminar todos los cursos, false en caso contrario
Restricciones
1 ≤ numCourses ≤ 1051 ≤ prerequisites.length ≤ 5000- Cada par
[a, b]tiene0 ≤ a, b < numCourses. - Ningún par aparece dos veces.
- Un par puede nombrar el mismo curso dos veces,
[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, y el curso 1 libera tanto el 2 como el 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 curso 2 espera al 1 y el curso 1 espera al 0. Los tres se esperan entre sí en un ciclo, así que ninguno puede ser el primero que tomes.
+20 pruebas ocultas al enviar
Para ir más allá
En un período caben cualquier cantidad de cursos, siempre que los requisitos previos de cada curso se hayan completado en períodos anteriores. ¿Cuál es el menor número de períodos que permite cursar 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 desdebhastaa. ¿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 espera todavía cada curso. Inicia una cola con los cursos cuyo conteo es 0 y, cada vez que proceses uno, reduce el conteo de todos los cursos que lo esperan. Si menos de
numCoursescursos llegan alguna vez a la cola, hay un ciclo.
Solución
Convierte los pares en un grafo dirigido con V = numCourses nodos y E = prerequisites.length aristas, una flecha b → a por cada par [a, b]. Se pueden terminar todos los cursos exactamente cuando ese grafo no tiene ciclos. El algoritmo de Kahn lo determina como lo planificaría un estudiante: sigue cursando una asignatura cuyas asignaturas prerrequisito ya estén todas aprobadas, y comprueba si te quedas sin cursos o sin opciones primero.
Toma todos los cursos gratuitos, ronda tras ronda
Correcto, pero no termina con las pruebas más grandes
Intuición
Planifica como lo haría un estudiante. En cada ronda, revisa todos los cursos que no hayas tomado. Si ya has tomado todos sus requisitos previos, tómalo. Repite hasta que una ronda no tome ninguno. Si para entonces has tomado todos los cursos, la respuesta es true.
Por qué una ronda estancada significa false: cuando una ronda no toma ningún curso, todos los cursos restantes tienen un requisito previo que también está entre los restantes. Empieza por cualquier curso restante y sigue avanzando hacia uno de sus requisitos previos que aún no hayas tomado. Nunca te quedarás sin pasos, y como hay un número limitado de cursos, volverás a un curso que ya hayas visitado. Eso es un ciclo, y los cursos que lo forman se esperan entre sí para siempre.
El método es correcto, pero en cada ronda vuelve a leer todos los pares y todos los cursos, y una ronda puede tomar tan solo un curso. Una cadena de 5,001 cursos, cada uno de los cuales necesita el anterior, requiere más de 5,000 rondas; entre 100,000 cursos, eso representa aproximadamente 5 × 10^8 comprobaciones, casi todas en cursos cuyo estado no cambió.
Algoritmo
- Marca todos los cursos como no cursados.
- Marca un curso como bloqueado si algún par le asigna un prerrequisito que no está cursado.
- Realiza todos los cursos que no estén cursados ni bloqueados.
- Si en esta ronda no se realizó 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
Un ciclo es un camino que vuelve al punto donde empezó. La búsqueda en profundidad encuentra uno recordando qué cursos están en el camino que está recorriendo en ese momento. Asigna a cada curso uno de tres estados: no visitado, en el camino actual y terminado.
Avanza desde un curso siguiendo sus flechas hasta los cursos que dependen de él. Marca un curso «en el camino» cuando llegues a él, y «terminado» cuando hayas explorado todas las flechas que salen de él y retrocedas. Una flecha hacia un curso que está en el camino significa que has recorrido un círculo: devuelve false. Una flecha hacia un curso terminado es segura, ya que se comprobó todo lo que se puede alcanzar desde él y no contiene ningún ciclo, así que la omites. Se visita cada curso una vez y se sigue cada flecha una vez.
Dos estados no bastan. En el rombo 0 → 1, 0 → 2, 1 → 3, 2 → 3, la búsqueda llega al curso 3 por segunda vez a través de 2, pero para entonces 3 ya está terminado, no está en el camino, y no hay ningún ciclo. Solo una flecha de vuelta al camino actual cierra un bucle.
Escribe la búsqueda con tu propia pila y, para cada curso, la posición de su siguiente flecha sin explorar. La versión recursiva es más corta, pero una cadena de 5,000 cursos tendría 5,000 llamadas de profundidad.
Algoritmo
- Construye, para cada curso, la lista de cursos que esperan que se complete.
- Para cada curso que no se haya visitado, márcalo en el camino y apílalo.
- 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, márcalo en el camino y apílalo.
- 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
Las rondas del primer enfoque pierden tiempo volviendo a comprobar los cursos que no cambiaron. Un curso queda libre en un único momento: cuando se toma su último prerrequisito. Así que cuenta, para cada curso, cuántos prerrequisitos aún le faltan; ese es su grado de entrada. Cuando tomes un curso, reduce el recuento de todos los cursos que dependen de él. Si un recuento baja a 0, ese curso queda libre en ese momento, así que lo añades a una cola.
Empieza la cola con todos los cursos cuyo recuento es 0 desde el principio y, después, ve sacando cursos de la cola hasta que quede vacía. En el primer ejemplo, los recuentos empiezan en 0, 1, 1, 1 para los cursos del 0 al 3. Al tomar el 0, el recuento del curso 1 baja a 0; al tomar el 1, los recuentos de los cursos 2 y 3 bajan a 0; se toman los cuatro, así que la respuesta es true. Cada curso entra en la cola como máximo una vez y cada par reduce un recuento una vez, así que el trabajo es O(V + E).
Por qué un curso pendiente significa que hay un ciclo: si la cola queda vacía mientras el curso a no se ha tomado, su recuento es mayor que 0, así que uno de sus prerrequisitos, b, tampoco se ha tomado. Lo mismo ocurre con b, y así sucesivamente. Un recorrido desde un curso hasta un prerrequisito no tomado nunca se detiene, así que vuelve a visitar un curso, lo que forma un ciclo. En el segundo ejemplo, ningún recuento empieza en 0, la cola empieza vacía y no se toma ninguno de los tres cursos.
También se cumple la dirección contraria: un curso que forma parte de un ciclo depende de otro curso del mismo ciclo, así que su recuento no puede llegar a 0 antes de que se tome ese otro curso, y ninguno de ellos va primero. Por tanto, «se toman todos los cursos» y «no hay ciclos» significan lo mismo. Además, 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.
- Pon en una cola cada curso cuyo grado de entrada sea 0.
- Saca un curso de la cola y cuéntalo. Reduce el grado de entrada de cada curso que espera a ese curso y agrega a la cola cada uno cuyo grado llegue a 0.
- Cuando la cola esté vacía, devuelve si el conteo 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
La mayoría de los errores se deben a invertir la dirección de un par, a una comprobación de ciclos demasiado estricta o a cursos que no aparecen en ningún par.
- Confundir la dirección.
[a, b]significa que b va primero, así que la flecha va de b a a y el grado de entrada de a aumenta. Construir las listas en una dirección y contar los grados de entrada en la otra rompe el algoritmo. - 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 cuentan. Inicia la cola con todos los cursos cuyo grado de entrada es 0, no solo con los que aparecen en algún par. - Un curso que es su propio prerrequisito,
[2, 2]. Es un ciclo de longitud uno: su grado de entrada nunca llega a 0 y la respuesta es false. - Usar dos estados en lugar de tres en la búsqueda en profundidad. En el rombo 0 → 1, 0 → 2, 1 → 3, 2 → 3, se llega al curso 3 dos veces, lo que parece un ciclo si solo registras los cursos «vistos». Solo una flecha que vuelve a la ruta actual cierra un ciclo.
- Usar recursión en cadenas largas. Una cadena de 5,000 cursos alcanza 5,000 llamadas de profundidad, superando el límite predeterminado de Python, que es 1,000.
- Devolver true cuando la cola se vacía sin comparar el número de cursos completados con
numCourses.
Preguntas frecuentes4
¿Cuál es la complejidad temporal del problema de programación 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. Crear las listas implica leer cada par una vez, cada curso entra en la cola como máximo una vez y cada par reduce un contador una vez. Las listas y los contadores ocupan O(V + E) espacio.
¿Por qué un curso que queda sin procesar en el algoritmo de Kahn significa que hay un ciclo?
Un curso solo queda pendiente si su recuento nunca llegó a 0, así que al menos uno de sus prerrequisitos también queda pendiente. Sigue esa espera de un curso a otro: cada paso llega a otro curso pendiente y, como hay un número finito de cursos, el recorrido debe volver a uno que ya ha visitado. El tramo entre las dos visitas es un ciclo.
¿Deberías usar BFS o DFS para Course Schedule?
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 proporciona gratis un orden válido de los cursos. La búsqueda en profundidad con tres estados es igual de rápida y es la opción natural cuando también tienes que informar del ciclo, porque los cursos de 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 de los cursos 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 un orden topológico.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
Python
def canFinish(numCourses, prerequisites):
# Escribe el código aquíCaso 1
Caso 2
Entrada
numCourses = 4 prerequisites = [[1, 0], [2, 1], [3, 1]]
Esperado
true