Graphes orientés sans cycles

Ecrire une fonction qui vérifie que le graphe est un dag.

Les dags peuvent représenter des étapes d'un processus (plus ou moins) complexe : un arc entre x et y veut dire "x doit être fait avant y". Par exemple, pour m'habiller le matin, je mets

• mon pantalon avant ma ceinture,
• ma chaussette droite avant la chaussure droite, idem pour la gauche,
• ma chemise avant ma ceinture,
• mon caleçon avant mon pantalon,
• mon pantalon avant chaque chaussure,
• ma chemise avant ma cravate,
• ma cravate avant mon pull,
• mon pull avant mon chapeau,
• ma montre n'importe quand.

Représenter le graphe.
Avec un tel graphe, on peut déterminer un ordre (non unique) dans lequel exécuter des actions : c'est le tri topologique. Ecrire une fonction qui renvoie un tableau donnant un ordre topologique.

On veut une fonction qui donne le nombre de chemins entre deux sommets s et t d'un dag.
Faire un tri topologique. Parcourir le tableau résultat, à partir de s, en propageant le nombre de chemins. Essayer sur le graphe suivant.