|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
14.12.2021, 00:12 | #1 |
Новичок
Джуниор
Регистрация: 13.12.2021
Сообщений: 1
|
C++ программа, которая по списку названий городов находит все наиболее длинные цепочки, которые можно из этого списка составить.
Задача:
Игра в «Города» заключается в следующем. Несколько игроков по очереди говорят название города. Начальная буква каждого следующего названия должна совпадать с последней буквой предыдущего. Никакой город не может быть назван дважды. Требуется написать программу, которая по списку названий городов находит все наиболее длинные цепочки, которые можно из этого списка составить. На стандартном потоке ввода задаётся сначала число N (0 ≤ N ≤ 10) — количество городов. В последующих N строках записаны название городов. Каждое из названий не превышает 20 символов и состоит из заглавных латинских букв. Названия городов могут повторяться, в этом случае города считаются различными и могут использоваться в цепочке столько раз, сколько раз они встречаются в списке. Кроме того, цепочки начинающиеся с каждого из них, считаются различными. На стандартный поток вывода требуется сначала вывести число K — длину максимально возможной цепочки. В последующих строках необходимо вывести названия всех городов, с которых могут начинаться цепочки длины K. Города в выводе не должны повторяться. Выводите города в том же порядке, в котором они встречались во входном файле. ___________________________________ ______________ Идея: заносим города в ориентированный граф и делаем DFS из каждой вершины, смотрим на глубину... Вот моя реализация, но такое решение падает, не подскажете где ошибка? Код:
|
14.12.2021, 20:29 | #2 |
Форумчанин
Регистрация: 25.01.2015
Сообщений: 472
|
Мне почему-то кажется, что требуется найти радиус графа, а он ищется через алгоритм Дейкстры или Флойда-Уоршалла - точно не помню.
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Программа, которая находит все натуральные числа, меньшие чем N, для которых выполняется соотношение a^2+b^2=c^2. | caliente | Помощь студентам | 0 | 13.03.2013 13:23 |
Паскаль-программа, которая продуцирует цепочки в трёхсимвольном алфавите с записью их в файл... | as1212 | Помощь студентам | 1 | 10.01.2012 11:32 |
Программа которая находит и печатает все группы знаков, в которые знак "*" входит не менее 2-х раз. | Scredis | Паскаль, Turbo Pascal, PascalABC.NET | 0 | 06.06.2011 22:47 |
Составить программу, которая формирует 2 списка, и написать процедуру присоединения 2го списка к 1му | Neitrosha | Помощь студентам | 7 | 25.02.2011 21:18 |
Составить рекурсивную функцию, которая находит цифровой корень целого числа. | Feran | Помощь студентам | 11 | 08.12.2010 00:31 |