Course Schedule
Il y a numCourses cours, numérotés de 0 à numCourses-1. Chaque paire [a, b] dans prerequisites signifie que tu dois terminer le cours b avant de commencer le cours a. Retourne true si un ordre te permet de terminer tous les cours, et false si aucun ne le permet.
Fonction
- numCoursesinteger
- le nombre de cours
- prerequisitesinteger-2d-array
- les paires [a, b], chacune indiquant que le cours b doit être suivi avant le cours a
- Renvoieboolean
- vrai si chaque cours peut être terminé, faux sinon
Contraintes
1 ≤ numCourses ≤ 1051 ≤ prerequisites.length ≤ 5000- Chaque paire
[a, b]vérifie0 ≤ a, b < numCourses. - Aucune paire n’apparaît deux fois.
- Une paire peut nommer deux fois le même cours,
[a, a]. Ce cours a besoin de lui-même en premier, donc il ne peut jamais être suivi.
Exemples
- Entrée
- numCourses = 4prerequisites = [[1, 0], [2, 1], [3, 1]]
- Sortie
- true
- Explication
- Le cours 0 n’a pas de prérequis, vous le suivez donc en premier. Cela libère le cours 1, qui libère les cours 2 et 3 ; l’ordre 0, 1, 2, 3 convient donc.
- Entrée
- numCourses = 3prerequisites = [[0, 2], [2, 1], [1, 0]]
- Sortie
- false
- Explication
- Le cours 0 attend le 2, le 2 attend le 1 et le 1 attend le 0. Les trois s’attendent mutuellement en boucle, donc aucun ne peut commencer en premier.
Pour aller plus loin
N'importe quel nombre de cours peut être suivi au cours d'un même semestre, à condition que les prérequis de chaque cours aient été remplis lors de semestres précédents. Quel est le nombre minimal de semestres nécessaires pour suivre tous les cours ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
Représente chaque cours par un point et chaque paire
[a, b]par une flèche allant debàa. Quelle forme dans ce dessin rendrait impossible de terminer ?Une boucle de flèches. Chaque cours d’une boucle attend un autre cours de la même boucle, donc aucun ne peut jamais passer en premier. La question est de savoir si le graphe contient un cycle.
Comptez le nombre de prérequis qu’il reste à chaque cours. Commencez une file avec les cours dont le nombre est égal à 0, puis, chaque fois que vous en prenez un, diminuez le nombre de chaque cours qui en dépend. Si moins de
numCoursescours atteignent la file, il y a un cycle.
Solution
Trace une flèche b → a pour chaque paire [a, b]. Chaque cours peut être terminé si et seulement si ce graphe, avec V = numCourses nœuds et E = prerequisites.length flèches, ne contient aucun cycle. L’algorithme de Kahn le vérifie comme le ferait un étudiant qui planifie son parcours : il continue à suivre un cours dont les prérequis sont remplis, puis vérifie si tous les cours sont suivis.
Suivez chaque cours gratuit, tour après tour
Correcte, mais ne termine pas sur les plus gros tests
Intuition
À chaque tour, prenez tous les cours non encore suivis dont tous les prérequis ont été suivis. Arrêtez-vous lorsqu’un tour ne prend aucun cours, et répondez true si tous les cours ont été suivis. Un tour ne prend aucun cours uniquement lorsque chaque cours restant dépend d’un autre cours restant, ce qui constitue un cycle.
À chaque tour, on relit toutes les paires et tous les cours, alors qu’un seul cours peut être pris. Une chaîne de 5,001 cours parmi 100,000 nécessite plus de 5,000 tours : environ 5 × 10^8 vérifications.
Algorithme
- Marquez chaque cours comme non suivi.
- Marquez un cours comme bloqué si une paire quelconque lui impose un prérequis qui n’est pas suivi.
- Suivez chaque cours qui n’est ni suivi ni bloqué.
- Si le tour n’a rien suivi, arrêtez ; sinon, revenez à l’étape 2.
- Renvoyez true si chaque cours est suivi.
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 == numCoursesRecherche en profondeur avec trois états
Intuition
La recherche en profondeur détecte un cycle en suivant le chemin qu’elle parcourt. Attribue à chaque cours l’un de ces trois états : non visité, sur le chemin, terminé. Suis les flèches d’un cours vers les cours qui en dépendent. Marque un cours comme étant sur le chemin lorsque tu y entres, puis comme terminé lorsque toutes ses flèches ont été explorées.
Une flèche vers un cours déjà sur le chemin ferme une boucle : renvoie false. Une flèche vers un cours terminé ne pose pas de problème, car tout ce qui est accessible depuis ce cours a été vérifié et ne contient aucun cycle ; ainsi, atteindre deux fois un cours ne constitue pas en soi un cycle. Chaque cours est visité une fois et chaque flèche suivie une fois : O(V + E).
Algorithme
- Construis, pour chaque cours, la liste des cours qui attendent celui-ci.
- Pour chaque cours qui n’a pas été visité, marque-le sur le chemin et empile-le.
- Regarde le sommet de la pile. S’il ne lui reste aucune flèche, marque-le comme terminé et dépile-le ; sinon, suis sa prochaine flèche.
- Si la flèche mène à un cours présent sur le chemin, return false. Si elle mène à un cours qui n’a pas été visité, marque ce cours sur le chemin et empile-le.
- Lorsque tous les cours sont terminés, return 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 TrueAlgorithme de Kahn
Intuition
Un cours devient disponible à un instant précis : lorsque son dernier prérequis a été suivi. Il faut donc conserver le degré entrant de chaque cours, c’est-à-dire le nombre de prérequis qu’il attend encore, et initialiser une file avec chaque cours dont le compte est égal à 0. Suivre un cours diminue le compte de chaque cours qui l’attend, et tout compte qui atteint 0 rejoint la file. Dans le premier exemple, les comptes commencent à 0, 1, 1, 1 : suivre 0 libère 1, et suivre 1 libère 2 et 3. Chaque cours entre une fois dans la file et chaque paire diminue un compte une fois : O(V + E).
Si la file se vide alors que le cours a n’a pas été suivi, son compte est supérieur à 0 : un prérequis de a n’a donc pas été suivi non plus, et ainsi de suite. Ce parcours doit repasser par un cours : c’est un cycle. À l’inverse, chaque cours d’un cycle attend un autre cours du même cycle, donc aucun ne peut être suivi en premier. L’ordre dans lequel les cours quittent la file constitue un programme valide.
Algorithme
- Pour chaque paire [a, b], ajoutez a à la liste des cours qui attendent b, et ajoutez 1 au degré entrant de a.
- Placez dans une file d’attente chaque cours dont le degré entrant est 0.
- Retirez un cours de la file d’attente et comptez-le. Diminuez le degré entrant de chaque cours qui l’attend, et ajoutez à la file d’attente chacun de ceux dont le degré atteint 0.
- Lorsque la file d’attente est vide, renvoyez si le compte est égal à
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
Pièges et cas limites
- Confondre le sens.
[a, b]signifie que b vient en premier : la flèche va de b vers a, et le degré entrant de a augmente. - Oublier les cours qui n’apparaissent dans aucune paire. Avec
numCourses = 5et l’unique paire[4, 3], les cours 0, 1 et 2 doivent aussi être placés dans la file au départ. - Utiliser deux états au lieu de trois dans le parcours en profondeur. Dans le losange 0 → 1, 0 → 2, 1 → 3, 2 → 3, le cours 3 est atteint deux fois et semble former un cycle si vous ne suivez que les éléments « vus ».
- Récursion sur une chaîne de 5 000 cours : 5 000 appels de profondeur, au-delà de la limite par défaut de Python, qui est de 1 000.
- Renvoyer true lorsque la file est vide sans vérifier que
numCoursescours ont été suivis. Le deuxième exemple renverrait true.
Questions fréquentes3
Quelle est la complexité temporelle du problème d’ordonnancement des cours ?
O(V + E), où V est le nombre de cours et E le nombre de paires, avec l’algorithme de Kahn ou une recherche en profondeur d’abord. Chaque paire est lue une fois, et chaque cours est traité une fois. Les listes et les compteurs occupent un espace de O(V + E).
Faut-il utiliser BFS ou DFS pour Course Schedule ?
Les deux s’exécutent en O(V + E). L’algorithme de Kahn, la version en largeur d’abord, ne présente aucun risque lié à la profondeur de récursion et te donne un ordre valide des cours. Le parcours en profondeur avec trois états est le choix naturel lorsque tu dois également signaler le cycle, car les cours présents dans sa pile le forment.
Qu’est-ce qu’un tri topologique ?
Un ordre des nœuds d’un graphe orienté dans lequel chaque flèche pointe vers l’avant ; ici, un ordre dans lequel chaque prérequis précède le cours qui en a besoin. Il existe exactement lorsque le graphe ne contient aucun cycle, et l’ordre dans lequel l’algorithme de Kahn prend les cours en est un. Course Schedule demande si un tel ordre existe.
Problèmes similaires
Des problèmes qui reposent sur les mêmes idées. En résoudre deux ou trois, c’est ce qui ancre un schéma.
def canFinish(numCourses, prerequisites):
# Écrivez le code iciTest #1
Test #2
Arguments
numCourses = 4 prerequisites = [[1, 0], [2, 1], [3, 1]]
Résultat attendu
true