Гамильтонов цикл
Вам дан неориентированный граф с
n вершинами и e рёбрами. Ваша задача — определить, содержит ли этот граф гамильтонов цикл.💡
Гамильтонов цикл — это путь, который начинается и заканчивается в одной и той же вершине, проходя при этом через каждую вершину ровно один раз.
Входные данные
Первая строка содержит два целых числа
n (1 ≤ n ≤ 20) и e (0 ≤ e ≤ ), которые обозначают количество вершин и рёбер в графе соответственно.В следующих
e строках описаны рёбра графа. Каждая такая строка содержит два целых числа a и b (1 ≤ a, b ≤ n, a ≠ b), указывающие на ребро между вершинами a и b.Выходные данные
Выведите
YES, если в графе существует гамильтонов путь или цикл. В противном случае выведите NO.Примеры
Входные данные | Выходные данные |
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