Cycle Hamiltonien
On vous donne un graphe non orienté composé de
n nœuds et e arêtes. Votre tâche consiste à déterminer si ce graphe contient un cycle hamiltonien.💡
Un cycle hamiltonien est un chemin qui commence et se termine au même nœud, en visitant chaque nœud exactement une fois.
Entrée
La première ligne contient deux entiers
n (1 ≤ n ≤ 20) et e (0 ≤ e ≤ ), qui correspondent respectivement au nombre de nœuds et d’arêtes du graphe.Les
e lignes suivantes indiquent les arêtes du graphe. Chaque ligne contient deux entiers a et b (1 ≤ a, b ≤ n, a ≠ b), qui décrivent une arête reliant les nœuds a et b.Sortie
Affichez
YES si le graphe contient un chemin ou un cycle hamiltonien. Sinon, affichez NO.Exemples
Entrée | Sortie |
3 3
1 2
2 3
3 1 | YES |
4 4
1 2
2 3
3 1
2 4 | NO |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB