Намиране на Хамилтонов цикъл в граф
Условие
Имаме ненасочен граф 𝐺(𝑉,𝐸)G(V,E), където 𝑉 е множеството от върхове, а 𝐸 е множеството от ребра. Трябва да проверим дали съществува Хамилтонов цикъл в графа 𝐺. Хамилтонов цикъл е цикъл, който посещава всеки връх точно веднъж и се връща в началния връх.
Вход:
Първият ред на входа съдържа две цели числа 𝑛 и 𝑚 – броят на върховете и броят на ребрата в графа, съответно.
Следващите 𝑚 реда съдържат по две цели числа 𝑢 и 𝑣 (1 ≤ 𝑢,𝑣≤ 𝑛), което означава, че има ребро между върховете 𝑢 и 𝑣.
Изход:
Ако съществува Хамилтонов цикъл, изведете “YES”. В противен случай изведете “NO”.
Пример:
Вход
5 6
1 2
2 3
3 4
4 5
5 1
2 4
Изход
YES
Вход
4 4
1 2
2 3
3 4
4 1
Изход
NO