Vérifier si le graphe est efficace
Étant donné un graphe non orienté avec
v sommets et e arêtes, il s’agit de déterminer s’il est « efficace ». Un graphe est considéré efficace s’il est possible de se déplacer d’un nœud quelconque à n’importe quel autre nœud en empruntant au plus 2 arêtes.Entrée
La première ligne de l’entrée contient deux entiers
v (1 ≤ v ≤ 100) et e (1 ≤ e ≤ 10 000).Les
e lignes suivantes contiennent des paires d’entiers v1, v2 (1 ≤ v1, v2 ≤ v) qui représentent une arête entre v1 et v2.Sortie
Le programme doit afficher
Yes si le graphe est efficace, et No dans le cas contraire.Exemples
Entrée | Sortie |
4 3
1 2
2 3
3 1 | No |
4 4
1 2
2 3
3 1
1 4 | Yes |
Explication
- Le sommet 4 n’est pas raccordé aux autres ⇒ il n’est pas possible de l’atteindre (ou d’en partir) avec un maximum de 2 arêtes.
- Il est possible de rejoindre n’importe quel sommet à partir de n’importe quel autre sommet en empruntant au plus 2 arêtes.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB