Vérifier si le graphe est biparti
On dit qu’un graphe est biparti s’il est possible de le colorier à l’aide de deux couleurs de manière à ce qu’aucun couple de sommets adjacents ne partage la même couleur.
Déterminer si un graphe est biparti permet de repérer des structures et des propriétés particulières, ce qui facilite la résolution de problèmes dans des domaines tels que la planification, l’allocation de ressources ou la gestion de conflits. Les graphes bipartis autorisent également l’utilisation d’algorithmes plus simples et d’optimisations dans des tâches comme la correspondance maximale (maximum matching) ou le coloriage de graphes.
On vous donne un graphe non orienté avec
v sommets et e arêtes. Vous devez vérifier si ce graphe est biparti ou non.Entrée
La première ligne de l’entrée contient deux entiers
v (1 ≤ v ≤ 100 000) et e (1 ≤ e ≤ 100 000).Les
e lignes suivantes contiennent chacune une paire d’entiers v1, v2 (1 ≤ v1, v2 ≤ v), ce qui signifie que le sommet v1 est relié au sommet v2, et inversement.Sortie
Le programme doit afficher
Yes si le graphe donné est biparti, et No dans le cas contraire.Exemples
Input | Output |
2 1
2 1 | Yes |
3 2
2 1
1 3 | Yes |
3 3
1 2
1 3
2 3 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB