Задача 102895
|
Название задачи: Игра в города . |
 |
Условие
Всем известны правила игры «в города»: первый игрок называет произвольный город, следующий – город, название которого начинается на ту же букву, на которую заканчивается название предыдущего города, и т.д. Аналогичным образом можно играть не в названия городов, а, например, в названия животных. Задан список допустимых для описанной игры слов, слова в нем могут повторяться. Напишите программу, определяющую, в каком порядке в процессе игры должны быть названы слова из списка, чтобы каждое слово было использовано ровно столько раз, сколько оно в нем встречается.Входные данные
В первой строке входного файла записано целое число N – количество слов в списке (1 ≤ N ≤ 1000), а в последующих N строках – сами слова. Каждое из них является последовательностью не более чем из 10 строчных английских букв.
Выходные данные
Выведите в выходной файл слова в искомом порядке, либо сообщение «NO», если такого порядка не существует. Каждое слово должно быть выведено в отдельную строку выходного файла.
Пример входного файла
4
b
ab
bc
bb
Пример выходного файла
ab
bb
b
bc
Решение
Скачать архив тестов и решенийСоставим ориентированный мультиграф (мультиграфом называется граф, в котором пары вершин могут быть соединены более чем одним ребром), вершинами которого будут являться буквы от a до z. Каждому слову из списка сопоставим ребро, соединяющее первую и последнюю буквы этого слова. В полученном мультиграфе требуется найти эйлеров путь (т.е. путь, проходящий по каждому ребру ровно один раз). Алгоритм построения такого пути можно найти, например, в [Липский 88, п. 2.7].
