Prépa Code Connexion Inscription

Écrire une fonction a_cycle : int list array -> bool qui détermine si un graphe non orienté contient un cycle.

Représentation : le graphe est un tableau adj de type int list array (liste d'adjacence). Les sommets sont numérotés de 0 à n-1.

Rappel : un cycle dans un graphe non orienté est un chemin fermé de longueur $\geq 3$ qui ne passe pas deux fois par la même arête. Le graphe peut être non connexe : il faut vérifier toutes les composantes.

Indication : lors d'un parcours en profondeur, un cycle est détecté lorsqu'on rencontre un voisin déjà visité qui n'est pas le père dans l'arbre de parcours.