Эйлерова дорожка, расстановка слов

Question

На каждой двери большое количество магнитных пластин.На каждой табличке написано одно слово.Таблички должны быть расположены в такой последовательности, чтобы каждое слово начиналось с той же буквы, что и предыдущее слово.Например, за словом acm может следовать слово motorola.

Например: skenzo logicboxes orderbox

ans: возможен заказ

Я знаю, что эта проблема связана с эйлеровым путем.Но я не могу это реализовать.Может кто-нибудь сказать мне, как это может быть реализовано.Означает, как я должен сделать граф и какие узлы должны быть связаны.Я знаю, что должен использовать матрицу смежности, но какие узлы должны быть связаны.

Answer 1

СЛОВА1, если я правильно помню.Вопреки некоторым другим, я согласен, что вам нужен путь Эйлера, а не гамильтониан.В полученном графе слова - это ребра (от первой буквы до последней), а буквы (удобно только строчные буквы от 'a' до 'z' в ASCII) вершины.

На самом деле, что выхотите, это не сам путь, вы хотите знать только, есть ли он.Поэтому вам нужны необходимые и достаточные условия на графе для существования эйлерова пути.

Очевидно, что для существования такого пути граф должен быть связан.Вы можете эффективно определить это с помощью объединения, находящегося .
. Тогда существование такого пути налагает условия на входные и выходные точки вершин.Если вы сформулируете эти условия правильно, а) они необходимы и достаточны, б) их легко проверить.

Веселее найти условия самостоятельно, но вы также можете найти их в статье в Википедии об Эйлериане.пути.

Answer 2

Коды Ascii первого и последнего символов могут использоваться в качестве вершин графа. Вы можете попробовать использовать DFS для упорядочения вершин и затем проверить, все ли вершины упорядочены. Если так, то все слова могут быть расположены в таком порядке.