Ciclo Hamiltoniano
Vi viene fornito un grafo non orientato con
n nodi ed e archi. Il vostro compito è determinare se esiste un ciclo Hamiltoniano all’interno del grafo.💡
Un ciclo Hamiltoniano è un percorso che inizia e termina nello stesso nodo, visitando ogni nodo esattamente una volta.
Input
La prima riga contiene due interi
n (1 ≤ n ≤ 20) ed e (0 ≤ e ≤ ) che indicano rispettivamente il numero di nodi e il numero di archi del grafo.Le successive
e righe descrivono gli archi del grafo. Ogni riga contiene due interi a e b (1 ≤ a, b ≤ n, a ≠ b), che indicano un arco tra i nodi a e b.Output
Stampate
YES se il grafo contiene un percorso o un ciclo Hamiltoniano. In caso contrario, stampate NO.Esempi
Input | Output |
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