poor_yorik, только все-таки надо брать не mat['А'..'Я','А'..'Я'], а как я предложил (см. выше) т.к. у меня матрица меньше получится. А что в элементах хранить - не суть важно (из двух этих вариантов). Либо там храняться дуги с номерами (номер слова) - мой вариант, либо там хранится количество дуг (твой вариант), но в твоем варианте придется востанавливать последовательность слов по найденным дугам - это выйдет немного дольше

Представте себе города на карте. Рассмотрим все пары городов. Если последняя буква названия первого города совпадает с первой буквой названия второго города, то проложим между ними дорогу с односторонним движением. Таким образом на карте возникнет сеть дорог с односторонним движением (ориентированный граф).

В такой интерпретации задача превращается в классическую задачу о комивояжере. То есть человеку надо посетить возможно большое количество городов и не побывав дважды ни в одном из них.

Задача вообще говоря NP-полна. Но метод ветвей и границ решает ее довольно быстро.(хотя и не полиномиально). Метод ветвей и границ конкретно для этой задачи преращается в рекурсивный обход ориентированного графа в глубину.

это задача класса P Space поэтому полный перебор