Tri topologique
Étant donné un graphe orienté comportant
v sommets et e arêtes, vous souhaitez organiser les sommets dans un ordre précis. Si une arête va du sommet v1 vers le sommet v2, alors le sommet source v1 doit apparaître plus tôt dans la liste que v2. Autrement dit, après le tri, chaque arête doit mener d’un sommet ayant un indice plus petit vers un sommet ayant un indice plus grand.🤔
Notez qu’il peut exister plusieurs ordres de tri topologique valides.
En revanche, s’il y a des cycles dans le graphe, aucun ordre de tri topologique valide n’existe.
L’algorithme peut s’implémenter avec un DFS (parcours en profondeur) qui démarre depuis chaque sommet non encore visité. À chaque appel DFS, on commence par appeler récursivement DFS sur tous les nœuds enfants du sommet courant, puis seulement lorsque tous ces nœuds enfants ont été traités, on ajoute le sommet courant à la liste de résultat. Cela garantit que le sommet source apparaît plus tard que tous ceux qui en dépendent. À la fin de l’algorithme, on inverse l’ordre dans la liste de résultat :
used = [False] * n # sommets déjà visités
order = [] # ordre topologique
def dfs(v): # DFS
used[v] = True # marquer le sommet comme visité
for to in g[v]: # pour chaque sommet to adjacent à v
if not used[to]: # si to n'est pas encore visité
dfs(to) # lancer un DFS depuis to
order.append(v) # ajouter v à l'ordre topologique
for i in range(n): # pour chaque sommet
if not used[i]: # s'il n'est pas encore visité
dfs(i) # lancer un DFS depuis ce sommet
print(*order[::-1]) # afficher l'ordre topologiqueDéfi : Organiser le planning de cours
On vous donne
n cours que vous souhaitez suivre. Il existe en tout p prérequis. Chaque prérequis est représenté par une paire de cours , ce qui signifie que vous devez valider le cours avant de suivre le cours (par exemple, si la paire est 1, 2, cela veut dire qu’il faut d’abord prendre le cours 2, puis le cours 1).Vous devez déterminer s’il est possible de terminer tous les cours.
Entrée
La première ligne de l’entrée contient deux entiers
n et p (1 ≤ n, p ≤ 10 000).Les
p lignes suivantes contiennent des paires d’entiers (1 ≤ ≤ n).Sortie
Le programme doit afficher
Yes s’il est possible de suivre la totalité des cours et No sinon.Exemples
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