Course Schedule
Ci sono numCourses corsi, numerati da 0 a numCourses-1. Ogni coppia [a, b] in prerequisites significa che devi completare il corso b prima di iniziare il corso a. Restituisci true se esiste un ordine che ti permette di completare tutti i corsi, e false se non esiste.
Funzione
- numCoursesinteger
- il numero di corsi
- prerequisitesinteger-2d-array
- le coppie [a, b], ciascuna delle quali indica che il corso b viene prima del corso a
- Restituisceboolean
- true se ogni corso può essere completato, false altrimenti
Vincoli
1 ≤ numCourses ≤ 1051 ≤ prerequisites.length ≤ 5000- Ogni coppia
[a, b]soddisfa0 ≤ a, b < numCourses. - Nessuna coppia compare due volte.
- Una coppia può indicare due volte lo stesso corso,
[a, a]. Quel corso dovrebbe essere completato prima di se stesso, quindi non può mai essere seguito.
Esempi
- Input
- numCourses = 4prerequisites = [[1, 0], [2, 1], [3, 1]]
- Output
- true
- Spiegazione
- Il corso 0 non ha prerequisiti, quindi lo segui per primo. Questo sblocca il corso 1, che sblocca il 2 e il 3, quindi l’ordine 0, 1, 2, 3 funziona.
- Input
- numCourses = 3prerequisites = [[0, 2], [2, 1], [1, 0]]
- Output
- false
- Spiegazione
- Il corso 0 aspetta il 2, il 2 aspetta l’1 e l’1 aspetta lo 0. I tre si aspettano a vicenda in un ciclo, quindi nessuno di loro può iniziare per primo.
Per approfondire
È possibile inserire un numero qualsiasi di corsi in un semestre, purché i prerequisiti di ciascun corso siano stati completati nei semestri precedenti. Qual è il numero minimo di semestri necessario per completare tutti i corsi?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Disegna ogni corso come un punto e ogni coppia
[a, b]come una freccia dabaa. Quale forma in quel disegno renderebbe impossibile completare il percorso?Un ciclo di frecce. Ogni corso in un ciclo aspetta un altro corso dello stesso ciclo, quindi nessuno di essi può mai essere il primo. La domanda è se il grafo contiene un ciclo.
Conta quanti prerequisiti ogni corso deve ancora soddisfare. Inizia una coda con i corsi il cui conteggio è 0 e, ogni volta che ne prendi uno, diminuisci il conteggio di ogni corso che lo aspetta. Se meno di
numCoursescorsi raggiungono la coda, c’è un ciclo.
Soluzione
Disegna una freccia b → a per ogni coppia [a, b]. Ogni corso può essere completato se e solo se questo grafo, con V = numCourses nodi ed E = prerequisites.length frecce, non ha cicli. L'algoritmo di Kahn lo verifica come farebbe uno studente con il suo piano: continua a seguire un corso di cui ha già completato i prerequisiti e controlla se riesce a seguire tutti i corsi.
Segui ogni corso gratuito, round dopo round
Corretto, ma non termina sui test più grandi
Intuizione
In ogni turno, prendi ogni corso non ancora preso i cui prerequisiti sono tutti stati soddisfatti. Fermati quando un turno non prende nulla e rispondi true se sono stati presi tutti i corsi. Un turno non prende nulla solo quando ogni corso rimanente è in attesa di un altro corso rimanente, il che costituisce un ciclo.
Ogni turno ricontrolla ogni coppia e ogni corso, eppure può prendere un solo corso. Una catena di 5,001 corsi tra 100,000 richiede oltre 5,000 turni: circa 5 × 10^8 controlli.
Algoritmo
- Segna ogni corso come non seguito.
- Segna un corso come bloccato se qualche coppia gli assegna un prerequisito che non è stato seguito.
- Segui ogni corso che non è stato né seguito né bloccato.
- Se il ciclo non ha seguito nessun corso, fermati; altrimenti torna al passaggio 2.
- Restituisci true se tutti i corsi sono stati seguiti.
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 == numCoursesRicerca in profondità con tre stati
Intuizione
La ricerca in profondità trova un ciclo tenendo traccia del percorso che sta seguendo. Assegna a ogni corso uno di tre stati: non visitato, sul percorso, completato. Segui le frecce da un corso ai corsi che dipendono da esso. Contrassegna un corso come sul percorso quando vi entri e come completato quando tutte le sue frecce sono state esplorate.
Una freccia verso un corso sul percorso chiude un ciclo: restituisci false. Una freccia verso un corso completato è sicura, perché tutto ciò che è raggiungibile da esso è stato controllato e non contiene cicli; quindi, un corso raggiunto due volte non costituisce di per sé un ciclo. Ogni corso viene raggiunto una volta e ogni freccia viene seguita una volta: O(V + E).
Algoritmo
- Costruisci, per ogni corso, l’elenco dei corsi che lo attendono.
- Per ogni corso non visitato, contrassegnalo sul percorso e inseriscilo in uno stack.
- Guarda l’elemento in cima allo stack. Se non ha più frecce, contrassegnalo come completato e rimuovilo; altrimenti segui la freccia successiva.
- Se la freccia porta a un corso sul percorso, return false. Se porta a un corso non visitato, contrassegna quel corso sul percorso e inseriscilo nello stack.
- Quando tutti i corsi sono completati, 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 TrueAlgoritmo di Kahn
Intuizione
Un corso diventa disponibile in un momento preciso: quando viene seguito il suo ultimo prerequisito. Quindi tieni traccia del grado entrante di ogni corso, cioè del numero di prerequisiti che deve ancora soddisfare, e inizializza una coda con tutti i corsi il cui conteggio è 0. Seguire un corso diminuisce il conteggio di ogni corso che lo aspetta, e un conteggio che raggiunge 0 entra nella coda. Nel primo esempio i conteggi iniziano da 0, 1, 1, 1: seguire 0 rende disponibile 1, e seguire 1 rende disponibili 2 e 3. Ogni corso entra nella coda una volta e ogni coppia diminuisce un conteggio una volta: O(V + E).
Se la coda si svuota mentre il corso a non è stato seguito, il suo conteggio è superiore a 0, quindi anche un prerequisito di a non è stato seguito, e così via. Questo percorso deve tornare a un corso già visitato: un ciclo. Viceversa, ogni corso appartenente a un ciclo aspetta un altro corso dello stesso ciclo, quindi nessuno può venire prima. L'ordine in cui i corsi escono dalla coda è una pianificazione valida.
Algoritmo
- Per ogni coppia [a, b], aggiungi a all’elenco dei corsi che attendono b e aggiungi 1 all’indegree di a.
- Inserisci in una coda ogni corso con indegree 0.
- Estrai un corso dalla coda e contalo. Diminuisci l’indegree di ogni corso che lo attende e aggiungi alla coda ciascuno che raggiunge 0.
- Quando la coda è vuota, restituisci se il conteggio è uguale 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
Trappole e casi limite
- Confondere la direzione.
[a, b]significa che b viene prima: la freccia va da b ad a e il grado entrante di a aumenta. - Dimenticare i corsi che non compaiono in nessuna coppia. Con
numCourses = 5e l'unica coppia[4, 3], anche i corsi 0, 1 e 2 devono essere inseriti nella coda all'inizio. - Usare due stati invece di tre nella ricerca in profondità. Nel rombo 0 → 1, 0 → 2, 1 → 3, 2 → 3, si raggiunge il corso 3 due volte, che sembra un ciclo se si tiene traccia solo di ciò che è "visto".
- Ricorrere lungo una catena di 5,000 corsi: 5,000 chiamate in profondità, oltre il limite predefinito di Python di 1,000.
- Restituire true quando la coda si svuota senza verificare che siano stati seguiti
numCoursescorsi. Il secondo esempio restituirebbe true.
Domande frequenti3
Qual è la complessità temporale del problema Course Schedule?
O(V + E), dove V è il numero di corsi ed E il numero di coppie, usando l'algoritmo di Kahn o la ricerca in profondità. Ogni coppia viene letta una volta e ogni corso viene gestito una volta. Gli elenchi e i conteggi occupano O(V + E) spazio.
È meglio usare BFS o DFS per Pianificazione dei corsi?
Entrambi hanno complessità O(V + E). L’algoritmo di Kahn, la versione con ricerca in ampiezza, non ha problemi di profondità della ricorsione e ti fornisce un ordine valido dei corsi. La ricerca in profondità con tre stati è la scelta naturale quando devi anche segnalare il ciclo, perché è formato dai corsi presenti nel suo stack.
Che cos'è un ordinamento topologico?
Un ordinamento dei nodi di un grafo diretto in cui ogni freccia punta in avanti; in questo caso, un ordinamento in cui ogni prerequisito precede il corso che ne ha bisogno. Esiste esattamente quando il grafo non contiene cicli, e l'ordine in cui l'algoritmo di Kahn prende i corsi è uno di questi. Course Schedule chiede se esiste un ordinamento di questo tipo.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def canFinish(numCourses, prerequisites):
# Scrivi il codice quiTest #1
Test #2
Argomenti
numCourses = 4 prerequisites = [[1, 0], [2, 1], [3, 1]]
Output atteso
true