Prépa Code Connexion Inscription

Écrire une fonction tri_topologique : int list array -> int list qui renvoie un tri topologique des sommets d'un graphe orienté acyclique (DAG).

Représentation : le graphe est un tableau adj de type int list array (liste d'adjacence), où adj.(i) est la liste des successeurs du sommet i. Les sommets sont numérotés de 0 à n-1.

Lorsque plusieurs sommets peuvent être choisis à une même étape (même degré entrant nul), on choisit celui de plus petit numéro.

Indication : l'algorithme de Kahn consiste à maintenir un tableau de degrés entrants, à sélectionner un sommet de degré entrant 0, le retirer du graphe et décrémenter les degrés de ses successeurs.