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 poter iniziare il corso a. Restituisci true se esiste un ordine in cui puoi 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 significa che il corso b viene prima del corso a
- Restituisceboolean
- vero se ogni corso può essere completato, falso altrimenti
Vincoli
1 ≤ numCourses ≤ 1051 ≤ prerequisites.length ≤ 5000- Ogni coppia
[a, b]ha0 ≤ a, b < numCourses. - Nessuna coppia compare due volte.
- Una coppia può indicare due volte lo stesso corso,
[a, a]. Quel corso ha bisogno di sé stesso prima, 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, e il corso 1 sblocca sia il 2 che 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 corso 2 aspetta l'1 e il corso 1 aspetta lo 0. I tre si aspettano a vicenda in un ciclo, quindi nessuno dei tre può essere il primo che segui.
+20 test nascosti all’invio
Per approfondire
È possibile inserire un numero qualsiasi di corsi in un semestre, purché i prerequisiti di ogni 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ù.
Rappresenta ogni corso con un punto e ogni coppia
[a, b]con una freccia dabaa. Quale forma nel disegno renderebbe impossibile finire?Un ciclo di frecce. Ogni corso in un ciclo aspetta un altro corso dello stesso ciclo, quindi nessuno può mai andare per primo. La domanda è se il grafo contiene un ciclo.
Conta quanti prerequisiti deve ancora soddisfare ogni corso. Avvia una coda con i corsi il cui conteggio è 0 e, ogni volta che ne prendi uno, diminuisci il conteggio di ogni corso che lo attende. Se meno di
numCoursescorsi raggiungono la coda, c'è un ciclo.
Soluzione
Trasforma le coppie in un grafo diretto con V = numCourses nodi ed E = prerequisites.length archi, una freccia b → a per ogni coppia [a, b]. È possibile completare tutti i corsi esattamente quando il grafo non contiene cicli. L'algoritmo di Kahn lo determina nel modo in cui pianificherebbe uno studente: continua a seguire un corso i cui prerequisiti sono stati tutti completati e verifica se finiscono prima i corsi o le opzioni.
Segui ogni corso gratuito, round dopo round
Corretto, ma non termina sui test più grandi
Intuizione
Pianifica come farebbe uno studente. In ogni turno, guarda ogni corso che non hai ancora seguito. Se hai seguito tutti i suoi prerequisiti, seguilo. Ripeti finché un turno non aggiunge nulla. Se a quel punto hai seguito tutti i corsi, la risposta è true.
Perché un turno bloccato significa false: quando un turno non aggiunge nulla, ogni corso rimanente ha un prerequisito che è anch’esso rimanente. Parti da un qualsiasi corso rimanente e continua a passare a uno dei suoi prerequisiti non ancora seguiti. Non finirai mai i passaggi e, poiché i corsi sono in numero limitato, tornerai a un corso che avevi già visitato. È un ciclo, e i corsi che ne fanno parte si aspettano a vicenda per sempre.
Il metodo è corretto, ma a ogni turno rilegge ogni coppia e ogni corso, e un turno può aggiungere anche un solo corso. Una catena di 5.001 corsi, ognuno dei quali richiede quello precedente, impiega oltre 5.000 turni; tra 100.000 corsi, si tratta di circa 5 × 10^8 controlli, quasi tutti su corsi il cui stato non è cambiato.
Algoritmo
- Segna ogni corso come non seguito.
- Segna un corso come bloccato se una coppia gli assegna un prerequisito non seguito.
- Segui ogni corso che non è né seguito né bloccato.
- Se il turno non ha seguito nulla, fermati; altrimenti torna al passaggio 2.
- Restituisci true se tutti i corsi sono 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
Un ciclo è un percorso che torna al punto da cui è partito. La ricerca in profondità ne trova uno ricordando quali corsi si trovano sul percorso che sta percorrendo in quel momento. Assegna a ogni corso uno di tre stati: non visitato, sul percorso corrente e completato.
Procedi da un corso seguendo le sue frecce verso i corsi che dipendono da esso. Contrassegna un corso come "sul percorso" quando lo raggiungi e come "completato" quando hai esplorato tutte le frecce che partono da esso e torni indietro. Una freccia verso un corso che si trova sul percorso significa che hai camminato in cerchio: restituisci false. Una freccia verso un corso completato è sicura, perché tutto ciò che è raggiungibile da quel corso è già stato controllato e non contiene cicli, quindi saltalo. Ogni corso viene raggiunto una volta e ogni freccia viene seguita una volta.
Due stati non bastano. Nel rombo 0 → 1, 0 → 2, 1 → 3, 2 → 3 la ricerca raggiunge il corso 3 una seconda volta passando per 2, ma a quel punto 3 è completato, non si trova sul percorso, e non c'è alcun ciclo. Solo una freccia che torna sul percorso corrente chiude un ciclo.
Scrivi la ricerca usando uno stack tuo e, per ogni corso, la posizione della sua prossima freccia non ancora esplorata. La versione ricorsiva è più breve, ma una catena di 5,000 corsi arriverebbe a una profondità di 5,000 chiamate.
Algoritmo
- Per ogni corso, crea l’elenco dei corsi che lo aspettano.
- Per ogni corso non visitato, contrassegnalo nel percorso e inseriscilo in uno stack.
- Guarda in cima allo stack. Se non ha più frecce, contrassegnalo come completato e rimuovilo dallo stack; altrimenti segui la freccia successiva.
- Se la freccia porta a un corso sul percorso, restituisci false. Se porta a un corso non visitato, contrassegna quel corso nel percorso e inseriscilo nello stack.
- Quando tutti i corsi sono completati, restituisci 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
I giri nel primo approccio sprecano tempo ricontrollando i corsi che non sono cambiati. Un corso si libera in un solo momento: quando viene completato il suo ultimo prerequisito. Quindi conta, per ogni corso, quanti prerequisiti deve ancora completare: il suo grado entrante. Quando completi un corso, riduci il conteggio di ogni corso che lo aspetta. Quando un conteggio scende a 0, significa che quel corso è libero in quel momento, quindi lo inserisci in una coda.
Inizia la coda con tutti i corsi il cui conteggio è 0 fin dall'inizio, poi estrai i corsi dalla coda finché non è vuota. Nel primo esempio i conteggi iniziali sono 0, 1, 1, 1 per i corsi da 0 a 3. Completare 0 porta il conteggio del corso 1 a 0; completare 1 porta i conteggi dei corsi 2 e 3 a 0; tutti e quattro vengono completati, quindi la risposta è true. Ogni corso entra nella coda al massimo una volta e ogni coppia riduce un conteggio una volta, quindi il lavoro è O(V + E).
Perché un corso rimanente significa che c'è un ciclo: se la coda si svuota mentre il corso a non è stato completato, il suo conteggio è maggiore di 0, quindi anche uno dei suoi prerequisiti, b, non è mai stato completato. Lo stesso vale per b, e così via. Un percorso dal corso a un prerequisito non completato non si ferma mai, quindi torna a un corso già visitato, formando un ciclo. Nel secondo esempio nessun conteggio parte da 0, la coda inizia vuota e nessuno dei tre corsi viene completato.
Vale anche il viceversa: un corso che fa parte di un ciclo aspetta un altro corso dello stesso ciclo, quindi il suo conteggio non può raggiungere 0 prima che quel corso venga completato, e nessuno di loro viene mai completato per primo. Quindi «completare tutti i corsi» e «non avere cicli» sono la stessa cosa. In più, 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 al grado entrante di a.
- Inserisci in una coda ogni corso con grado entrante 0.
- Estrai un corso dalla coda e conteggialo. Riduci il grado entrante di ogni corso che lo attende e aggiungi alla coda ciascuno di quelli 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
La maggior parte dei bug deriva dalla direzione di una coppia, da un controllo dei cicli troppo rigido o da corsi che non compaiono in nessuna coppia.
- Confondere la direzione.
[a, b]significa che b viene prima, quindi la freccia va da b ad a e il grado entrante di a aumenta. Costruire le liste in un verso e contare i gradi entranti nell'altro compromette l'algoritmo. - Dimenticare i corsi che non compaiono in nessuna coppia. Con
numCourses = 5e l'unica coppia[4, 3], i corsi 0, 1 e 2 contano comunque. Inizia la coda con tutti i corsi il cui grado entrante è 0, non solo quelli che hai visto in una coppia. - Un corso che è prerequisito di sé stesso,
[2, 2]. È un ciclo di lunghezza uno: il suo grado entrante non raggiunge mai 0 e la risposta è false. - 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, e questo sembra un ciclo se tieni traccia solo di ciò che è «visto». Solo una freccia che torna al percorso corrente chiude un ciclo.
- Ricorsione su catene lunghe. Una catena di 5.000 corsi comporta 5.000 chiamate in profondità, superando il limite predefinito di Python, pari a 1.000.
- Restituire true quando la coda si svuota senza confrontare il numero di corsi seguiti con
numCourses.
Domande frequenti4
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à. La creazione degli elenchi legge ogni coppia una volta, ogni corso entra nella coda al massimo una volta e ogni coppia riduce un conteggio una volta. Gli elenchi e i conteggi occupano O(V + E) spazio.
Perché un corso rimasto fuori nell’algoritmo di Kahn significa che c’è un ciclo?
Un corso rimane escluso solo se il suo conteggio non ha mai raggiunto 0, quindi anche almeno uno dei suoi prerequisiti rimane escluso. Segui questa attesa da un corso all'altro: ogni passaggio porta a un altro corso escluso e, dato che i corsi sono in numero finito, il percorso deve tornare a uno già visto. Il tratto tra le due visite è un ciclo.
Dovresti usare BFS o DFS per Course Schedule?
Entrambi hanno complessità O(V + E). L'algoritmo di Kahn, la versione in ampiezza, non ha profondità di ricorsione di cui preoccuparsi e ti fornisce gratuitamente un ordine valido dei corsi. La ricerca in profondità con tre stati è altrettanto veloce ed è 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 dei corsi in cui ogni prerequisito viene prima del corso che ne ha bisogno. Esiste esattamente quando il grafo non contiene cicli, e l’ordine in cui l’algoritmo di Kahn seleziona i corsi è un esempio. Course Schedule chiede se esiste un ordinamento topologico.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
Python
def canFinish(numCourses, prerequisites):
# Scrivi il codice quiCaso 1
Caso 2
Input
numCourses = 4 prerequisites = [[1, 0], [2, 1], [3, 1]]
Atteso
true