Ordinamento Topologico
Dato un grafo diretto con
v vertici e e archi, si desidera ordinare i vertici in un dato ordine. Se esiste un arco che va da v1 a v2, il vertice sorgente v1 deve apparire prima, nell’elenco dei vertici, rispetto a v2. In questo modo, una volta completato l’ordinamento dei vertici, ciascun arco porterà da un vertice con indice inferiore a uno con indice superiore.🤔
Nota che possono esistere diversi ordinamenti topologici validi.
D'altra parte, se il grafo contiene cicli, non esiste alcun ordinamento topologico valido.
L'algoritmo può essere implementato usando un DFS (Depth-First Search) che parte da ogni vertice non ancora visitato. In ciascuna iterazione del DFS, si aggiungono ricorsivamente prima tutti i nodi figli del vertice corrente e, soltanto dopo aver elaborato tutti i figli, si aggiunge il vertice corrente all’elenco dei risultati. Questo garantisce che il vertice sorgente compaia più tardi di tutti i vertici da esso raggiungibili. Al termine dell'algoritmo, si inverte l’ordine dell’elenco dei risultati:
used = [False] * n # vertici già utilizzati
order = [] # ordinamento topologico
def dfs(v): # DFS
used[v] = True # segna v come utilizzato
for to in g[v]: # per ogni vertice to adiacente a v
if not used[to]: # se to non è già utilizzato
dfs(to) # esegui DFS a partire da to
order.append(v) # aggiunge v all'ordinamento topologico
for i in range(n): # per ogni vertice
if not used[i]: # se i non è già utilizzato
dfs(i) # esegui DFS a partire da i
print(*order[::-1]) # stampa l'ordinamento topologicoSfida: Organizzare il Piano di Studi
Ti vengono dati
n corsi che desideri seguire. In totale ci sono p prerequisiti. Ogni prerequisito rappresenta una coppia di corsi , il che significa che devi seguire il corso prima di poter affrontare il corso (se la coppia è 1, 2, significa che devi prima seguire il corso 2 per poter seguire il corso 1).Devi verificare se è possibile completare tutti i corsi.
Input
La prima riga dell’input contiene due interi
n e p (1 ≤ n, p ≤ 10 000).Le successive
p righe contengono coppie di interi (1 ≤ ≤ n).Output
Il programma deve stampare
Yes se è possibile seguire tutti i corsi, altrimenti No.Esempi
Input | Output |
2 1
2 1 | Yes |
2 2
2 1
1 2 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB