|
|
ru.algorithms- RU.ALGORITHMS ---------------------------------------------------------------- From : Sergey Politov 2:5015/176.18 12 Dec 2001 06:30:19 To : Kartohin Ruslan Subject : Re: Гоpодская олимпиада по инфоpматике --------------------------------------------------------------------------------
KR> Hо вообще, я не помню упоминал или нет, необходимо было вывести все
KR> буквы с котоpых может начинаться и заканчиваться последовательность. То
KR> есть для твоего пpимеpа ответ один: a-a
Дык это совсем меняет дело. Задача переформулируется следующим образом. Дан
мульти
граф найти все возможные Эйлеровы циклы в нем, а в ответ выдавать не сами
циклы, а только
и начала и конец. А это вообще просто.
Hу во первых о формировании графа. Буквы - вершины, слова - ребра. Как не трудо
заметить
граф - ориентированный. Идем дальше. Вспоминаем критерий эйлеровости, во первых
если
не считать изолированных вершин, то граф должен быть связным. А дальше для
каждой вершины
считаем количество в нее входящих и выходящих из нее ребер, Путь существует
если из одной
вершины выходит на одно ребро больше, чем входит, а в одной вершине наоборот,
ну а у всех
остальных вершин эти количества равны. Тогда выдаем эти две вершины и делу
конец. Если же
для всех вершин это количесво равно(кол-во входящих и выходящих), то существует
Эйлеров
цикл и из кадой вершины обойдя все ребра мы вернемся в нее же.
Я надеюсь, что я был прав.
Bye ..
Sergey Politov
--- WP/95 Rus 1.78 Релиз 1 Reg.
* Origin: Metal Invaders. (2:5015/176.18)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/39910529fc0b.html, оценка из 5, голосов 10
|