Prépa Code Connexion Inscription

Écrire une fonction est_biparti : int list array -> bool qui détermine si un graphe non orienté est biparti.

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 graphe est biparti si on peut partitionner ses sommets en deux ensembles $U$ et $V$ tels que chaque arête relie un sommet de $U$ à un sommet de $V$. Par le théorème de König, cela revient à vérifier que le graphe ne contient aucun cycle de longueur impaire.

Indication : effectuer un parcours en largeur en coloriant les sommets avec 2 couleurs. Si un voisin a la même couleur que le sommet courant, le graphe n'est pas biparti. Attention : le graphe peut être non connexe, il faut traiter toutes les composantes.