Hamiltonscher Zyklus
Ihnen wird ein ungerichteter Graph mit
n Knoten und e Kanten gegeben. Ihre Aufgabe besteht darin festzustellen, ob der Graph einen Hamiltonschen Zyklus enthält.💡
Ein Hamiltonscher Zyklus ist ein Pfad, der an demselben Knoten beginnt und endet und jeden Knoten genau einmal besucht.
Eingabe
Die erste Zeile enthält zwei ganze Zahlen
n (1 ≤ n ≤ 20) und e (0 ≤ e ≤ ). Damit wird die Anzahl der Knoten beziehungsweise die Anzahl der Kanten im Graphen angegeben.Die nächsten
e Zeilen beschreiben die Kanten des Graphen. In jeder dieser Zeilen stehen zwei ganze Zahlen a und b (1 ≤ a, b ≤ n, a ≠ b), die eine Kante zwischen den Knoten a und b angeben.Ausgabe
Geben Sie
YES aus, wenn der Graph einen Hamiltonschen Pfad oder Zyklus enthält. Andernfalls geben Sie NO aus.Beispiele
Eingabe | Ausgabe |
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