Ciclo Hamiltoniano
É-lhe dado um grafo não direcionado com
n nós e e arestas. A sua tarefa é determinar se o grafo contém um ciclo Hamiltoniano.💡
Um ciclo Hamiltoniano é um caminho que começa e termina no mesmo nó, visitando cada nó exatamente uma vez.
Entrada
A primeira linha contém dois inteiros
n (1 ≤ n ≤ 20) e e (0 ≤ e ≤ ), que representam, respetivamente, o número de nós e o número de arestas do grafo.As seguintes
e linhas representam as arestas do grafo. Cada linha contém dois inteiros a e b (1 ≤ a, b ≤ n, a ≠ b), indicando uma aresta entre os nós a e b.Saída
Imprima
YES se o grafo contiver um caminho ou ciclo Hamiltoniano. Caso contrário, imprima NO.Exemplos
Entrada | Saída |
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