Условие:
Реями и её друзья
ограничение по времени на тест1 секунда
ограничение по памяти на тест256 мегабайт
Реями очень любила устраивать весёлые праздники для своих друзей. Однажды она решила собрать всех своих n
друзей за волшебным столом, который точно вмещал n
человек. Но не всё было так просто: среди её друзей были особые пары, которые давно дружили между собой. Всего было m
пар.
Реями захотела рассадить всех за столом так, чтобы каждая пара давних друзей сидела за соседними местами. За волшебным столом можно сидеть только с одной стороны.
Пример волшебного стола. Зеленым цветом показаны соседние места для синего места.
Теперь перед вами стоит задача помочь Реями: можно ли рассадить всех её друзей за волшебным столом так, чтобы каждая пара давних друзей сидела по соседству? Если это возможно, покажите, как это можно сделать.
Входные данные
В первой строке входных данных содержится два натуральных числа n
и m
(2≤n,m≤1000
) — число друзей Реями и количество пар давних друзей.
Во следующих m
строках содержится по два числа u
и v
(1≤u,v≤n
, u≠v
) — номера друзей, которые хотят сидеть рядом.
Гарантируется, что все пары (u,v)
различны.
Выходные данные
В единственной строке выходных данных выведите n
чисел p1,...,pn
— номера мест, на которых должны сидеть её друзья (друг под номером i
будет сидеть на pi
месте), если друзей возможно рассадить с пожеланиями Реями, и −1
иначе.
Решение:
Для решения задачи о рассадке друзей Реями за столом с учетом пар давних друзей, мы можем представить эту задачу в виде графа. Каждый друг будет представлять собой вершину, а пары друзей, которые хотят сидеть рядом, будут представлять собой ребра между этими вершинами.
Задача сводится к нахождению гамильтонова пути в графе, где каждая пара соседних вершин (друзей) должна быть связана ребром. Если такой путь существует, мы можем вывести порядок рассадки друзей. Если нет, то выводим -1.
Шаги решения:
1. Построить граф: Создать список смежности для представления графа.
2. Проверить возможность рассадки: Использовать алгоритм поиска в глубину (DFS) или поиск в ширину (BFS) для нахождения гамильтонова пути.
3. Вывести результат: Если путь найден, вывести порядок рассадки, иначе -1.
Вот пример реализации на Python:
1. : Мы используем для хранения списка смежности, где ключом является друг, а значением - список его соседей. 2. : Функция рекурсивно ищет путь, добавляя текущую вершину в . Если длина равна , значит, мы нашли подходящую рассадку. 3. : Мы пробуем начать поиск с каждой вершины, чтобы учесть все возможные варианты рассадки. 4. : Если путь найден, выводим его, иначе выводим -1. Этот алгоритм работает эффективно для заданных ограничений (n, m ≤ 1000).