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 pouvoir commencer le cours a. Renvoie true s’il existe un ordre dans lequel tu peux terminer tous les cours, et false s’il n’en existe aucun.
Fonction
- numCoursesinteger
- le nombre de cours
- prerequisitesinteger-2d-array
- les paires [a, b], chacune indiquant que le cours b précède le cours a
- Renvoieboolean
- vrai si tous les cours peuvent être terminés, 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 aucun prérequis, donc tu le suis en premier. Cela libère le cours 1, et le cours 1 libère à la fois les cours 2 et 3, donc l’ordre 0, 1, 2, 3 convient.
- Entrée
- numCourses = 3prerequisites = [[0, 2], [2, 1], [1, 0]]
- Sortie
- false
- Explication
- Le cours 0 attend le 2, le cours 2 attend le 1, et le cours 1 attend le 0. Les trois cours s’attendent mutuellement en boucle, donc aucun d’entre eux ne peut être le premier que tu suis.
+20 tests cachés à la soumission
Pour aller plus loin
N’importe quel nombre de cours peut être suivi pendant un trimestre, à condition que les prérequis de chaque cours aient été terminés lors de trimestres précédents. Quel est le nombre minimal de trimestres 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 debversa. 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 d’entre eux ne peut jamais commencer en premier. La question est de savoir si le graphe contient un cycle.
Compte le nombre de prérequis qu’il reste à chaque cours. Commence par mettre dans une file les cours dont le nombre est de 0, puis, chaque fois que tu en prends un, diminue le nombre de prérequis de chaque cours qui en dépend. Si moins de
numCoursescours finissent par atteindre la file, il y a un cycle.
Solution
Transforme les paires en un graphe orienté avec V = numCourses nœuds et E = prerequisites.length arêtes, une flèche b → a pour chaque paire [a, b]. Chaque cours peut être terminé si et seulement si ce graphe ne contient aucun cycle. L’algorithme de Kahn le détermine comme un étudiant organiserait son programme : continue à suivre un cours dont tous les prérequis sont terminés, et vois si tu viens à bout des cours ou si tu te retrouves d’abord sans options.
Suivez chaque cours gratuit, tour après tour
Correcte, mais ne termine pas sur les plus gros tests
Intuition
Planifie comme le ferait un étudiant. À chaque tour, examine tous les cours que tu n’as pas suivis. Si tous leurs prérequis ont été suivis, suis-les. Répète jusqu’à ce qu’un tour ne permette de suivre aucun cours. Si tous les cours ont alors été suivis, la réponse est true.
Pourquoi un tour bloqué signifie false : lorsqu’un tour ne permet de suivre aucun cours, chaque cours restant a un prérequis qui est lui aussi restant. Commence par n’importe quel cours restant et continue en passant à l’un de ses prérequis non suivis. Tu ne manqueras jamais d’étapes, et comme le nombre de cours est limité, tu reviendras à un cours déjà visité. C’est un cycle, et les cours qui en font partie s’attendent mutuellement pour toujours.
La méthode est correcte, mais à chaque tour, elle relit chaque paire et chaque cours, et un tour peut ne permettre de suivre qu’un seul cours. Une chaîne de 5,001 cours, chacun nécessitant celui qui le précède, prend plus de 5,000 tours ; parmi 100,000 cours, cela représente environ 5 × 10^8 vérifications, presque toutes portant sur des cours dont l’état n’a pas changé.
Algorithme
- Marquez chaque cours comme non suivi.
- Marquez un cours comme bloqué si une paire lui donne un prérequis qui n’est pas suivi.
- Suivez chaque cours qui n’est ni suivi ni bloqué.
- Si ce tour n’a rien ajouté, arrêtez-vous ; 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
Un cycle est un chemin qui revient à son point de départ. Le parcours en profondeur en trouve un en mémorisant les cours qui se trouvent sur le chemin qu’il parcourt à cet instant. Attribue à chaque cours l’un de ces trois états : non visité, sur le chemin actuel et terminé.
Depuis un cours, suis ses flèches vers les cours qui en dépendent. Marque un cours « sur le chemin » quand tu y arrives, et « terminé » quand toutes ses flèches sortantes ont été explorées et que tu reviens en arrière. Une flèche vers un cours qui se trouve sur le chemin signifie que tu as tourné en rond : renvoie false. Une flèche vers un cours terminé est sans danger, puisque tout ce qui est accessible depuis celui-ci a été vérifié et ne contient aucun cycle ; tu peux donc l’ignorer. Chaque cours est visité une fois et chaque flèche est suivie une fois.
Deux états ne suffisent pas. Dans le losange 0 → 1, 0 → 2, 1 → 3, 2 → 3, la recherche atteint le cours 3 une deuxième fois en passant par 2, mais 3 est alors terminé, et non sur le chemin, et il n’y a aucun cycle. Seule une flèche qui revient sur le chemin actuel ferme une boucle.
Écris la recherche avec ta propre pile et, pour chaque cours, la position de sa prochaine flèche inexplorée. La version récursive est plus courte, mais une chaîne de 5,000 cours nécessiterait une profondeur de 5,000 appels.
Algorithme
- Construis, pour chaque cours, la liste des cours qui en dépendent.
- Pour chaque cours qui n’a pas été visité, marque-le dans le chemin et empile-le.
- Regarde le sommet de la pile. S’il n’a plus de flèche à suivre, marque-le comme terminé et dépile-le ; sinon, suis sa prochaine flèche.
- Si la flèche mène à un cours présent dans le chemin, return false. Si elle mène à un cours qui n’a pas été visité, marque ce cours dans 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
Les tours de la première approche perdent du temps à revérifier les cours qui n’ont pas changé. Un cours n’est libéré qu’à un seul moment : lorsque son dernier prérequis est suivi. Comptez donc, pour chaque cours, le nombre de prérequis qu’il attend encore : son degré entrant. Lorsque vous suivez un cours, diminuez le compte de chaque cours qui l’attend. Un compte qui tombe à 0 signifie que le cours est libre dès maintenant ; vous le placez donc dans une file.
Commencez la file avec tous les cours dont le compte est égal à 0 dès le départ, puis retirez des cours de la file jusqu’à ce qu’elle soit vide. Dans le premier exemple, les comptes commencent à 0, 1, 1, 1 pour les cours 0 à 3. En suivant 0, le compte du cours 1 tombe à 0 ; en suivant 1, ceux des cours 2 et 3 tombent à 0 ; les quatre cours sont suivis, donc la réponse est true. Chaque cours entre dans la file au plus une fois et chaque paire diminue un compte une fois, donc le travail est O(V + E).
Pourquoi un cours restant implique un cycle : si la file se vide alors que le cours a n’a pas été suivi, son compte est supérieur à 0, donc l’un de ses prérequis, b, n’a pas non plus été suivi. Il en va de même pour b, et ainsi de suite. Un parcours d’un cours vers un prérequis non suivi ne s’arrête jamais, donc il revisite un cours, ce qui forme un cycle. Dans le deuxième exemple, aucun compte ne commence à 0, la file est vide au départ et aucun des trois cours n’est suivi.
La réciproque est également vraie : un cours faisant partie d’un cycle attend un autre cours du même cycle, donc son compte ne peut pas atteindre 0 avant que celui-ci soit suivi, et aucun d’entre eux ne passe jamais en premier. Ainsi, « tous les cours sont suivis » et « il n’y a pas de cycle » sont deux formulations équivalentes. En prime, l’ordre dans lequel les cours sortent de la file constitue un planning valide.
Algorithme
- Pour chaque paire [a, b], ajoutez a à la liste des cours qui attendent b, et ajoutez 1 au degré entrant de a.
- Mettez dans une file tous les cours dont le degré entrant est 0.
- Retirez un cours de la file et comptez-le. Diminuez le degré entrant de chaque cours qui l’attend, et ajoutez à la file chaque cours dont le degré entrant atteint 0.
- Lorsque la file est vide, renvoyez si le nombre 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
La plupart des bogues proviennent du sens d’une paire, d’une détection de cycle trop stricte ou de cours qui n’apparaissent dans aucune paire.
- Confondre le sens.
[a, b]signifie que b vient en premier, donc la flèche va de b à a et le degré entrant de a augmente. Construire les listes dans un sens et compter les degrés entrants dans l’autre casse l’algorithme. - Oublier les cours qui n’apparaissent dans aucune paire. Avec
numCourses = 5et l’unique paire[4, 3], les cours 0, 1 et 2 comptent toujours. Commence la file avec tous les cours dont le degré entrant est 0, pas seulement ceux qui apparaissent dans une paire. - Un cours qui est son propre prérequis,
[2, 2]. C’est un cycle de longueur un : son degré entrant n’atteint jamais 0 et la réponse est false. - 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, ce qui ressemble à un cycle si tu suis seulement les cours « visités ». Seule une flèche qui revient dans le chemin actuel ferme une boucle.
- La récursion sur de longues chaînes. Une chaîne de 5 000 cours entraîne 5 000 appels récursifs, dépassant la limite par défaut de Python, qui est de 1 000.
- Renvoyer true lorsque la file est vide sans comparer le nombre de cours suivis à
numCourses.
Questions fréquentes4
Quelle est la complexité temporelle du problème d’emploi du temps 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. La construction des listes lit chaque paire une fois, chaque cours entre dans la file au plus une fois, et chaque paire décrémente un compte une fois. Les listes et les comptes occupent un espace de O(V + E).
Pourquoi un cours restant à la fin de l’algorithme de Kahn signifie-t-il qu’il y a un cycle ?
Un cours ne reste que si son compteur n’a jamais atteint 0 ; au moins l’un de ses prérequis reste donc aussi. Suivez cette attente de cours en cours : chaque étape mène à un autre cours restant, et comme le nombre de cours est fini, le parcours doit revenir à un cours déjà visité. Le segment entre les deux visites est un cycle.
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 parcours en largeur, n’a pas de profondeur de récursion à prendre en compte et vous fournit gratuitement un ordre valide des cours. Le parcours en profondeur avec trois états est tout aussi rapide et constitue le choix naturel lorsque vous devez é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 des cours dans lequel chaque prérequis vient avant 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 s’il existe un ordre topologique.
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.
Python
def canFinish(numCourses, prerequisites):
# Écrivez le code iciCas 1
Cas 2
Entrée
numCourses = 4 prerequisites = [[1, 0], [2, 1], [3, 1]]
Attendu
true