Ciclo Hamiltoniano

Time Limit:
5 Sec
Memory Limit:
128Mb
Enviados:
69
Resuelto:
17
Enviar Estado

Descripción

Dado un grado no direccionado verificar si este tiene un ciclo hamiltoniano.

Un ciclo hamiltoniano es por definición un camino que recorre todos los nodos una sola vez, a exepción del primero que se visita dos veces.

 

Entrada

Leer casos de prueba hasta fin de archivo. Se garantiza que no habrá más de 20 casos de prueba.
Se da el número de nodos n y de aristas m. 1<=n<=20, 0<=m<=50. Seguido a esto m pares u y v denotando que existe un camino de u a v y viceversa.

 

Salida

Imprimir 1 si existe un camino hamiltoniano y 0 en el caso contrario.

 

Ejemplo Entrada

Copy icon 
8 13
0 1
0 2
0 3
0 6
1 6
1 7
2 3
2 7
2 6
3 4
3 5
6 7
4 5
4 4
0 1
0 2
1 2
2 3
5 5
0 1
0 2
1 2
2 3
2 4
1 0
2 0
3 3
0 1
1 0
1 2
6 6
0 3
3 4
3 1
3 2
2 1
4 5
3 3
0 1
1 2
2 0
5 9
0 1
0 2
1 4
2 3
3 4
4 3
4 2
2 1
2 3

Ejemplo Salida

Copy icon 
0
0
0
1
0
0
0
1
1

Ayuda