Le graphe se compose-t-il de cliques ?
Une clique est un sous-ensemble de sommets dans un graphe non orienté, où chaque paire de sommets distincts est connectée par une arête. En d'autres termes, une clique est un sous-graphe complet dans lequel tous les sommets sont adjacents les uns aux autres.
On vous donne un graphe non orienté possédant
v sommets et e arêtes. Nous souhaitons vérifier si ce graphe se présente comme un ensemble de cliques disjointes.Entrée
La première ligne de l'entrée contient deux entiers
v (1 ≤ v ≤ 1000) et e (1 ≤ e ≤ ).Les
e lignes suivantes contiennent des paires d'entiers v1, v2 (1 ≤ v1, v2 ≤ v), indiquant que le sommet v1 est relié au sommet v2 et inversement.Sortie
Le programme doit afficher
Yes si le graphe donné est une collection de cliques disjointes, et No sinon.Exemples
Entrée | Sortie |
3 3
1 2
2 3
1 3 | Yes |
5 4
1 2
2 3
1 3
4 5 | Yes |
5 5
1 2
2 3
1 3
3 4
4 5 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB