Форум программистов, компьютерный форум CyberForum.ru

Задача "Гонки по улицам" (обход ориентированного графа) - C++

Восстановить пароль Регистрация
 
s2df
0 / 0 / 0
Регистрация: 29.03.2013
Сообщений: 5
12.11.2013, 09:50     Задача "Гонки по улицам" (обход ориентированного графа) #1
Здравствуйте,помогите с задачей,если можно с комметарием,чтобы разобраться.Спасибо
На рисунке ниже изображен пример плана улиц для гонки. Вы видите точки, помеченные числами от 0 до N (где N = 9), а также стрелки, соединяющие их. Точка 0 является стартовой, а точка N - финишной. Стрелками представлены улицы с односторонним движением. Участники гонки передвигаются от точки к точке по улицам только в направлении стрелок. В каждой точке участник гонки может выбрать любую из исходящих стрелок.
Назовем план улиц "хорошим", если он обладает следующими свойствами:
1. Каждая точка плана может быть достигнута со старта.
2. Финиш может быть достигнут из любой точки плана.
3. У финиша нет исходящих стрелок.
Для достижения финиша участник не обязан пройти через все точки. Однако некоторые точки невозможно обойти. Назовем их "неизбежными". В примере такими точками являются точки 0, 3, 6 и 9. Для заданного "хорошего" плана ваша программа должна определить множество "неизбежных" точек (за исключением старта и финиша), которые должны посетить все участники (подзадача А).
Входные данные
"Хороший" план содержит не более 50 точек и не более 100 стрелок. На вход подается N+1 строка. Первые N строк содержат конечные точки точки стрелок, исходящих, соответственно, из точек от 0 до N-1. Каждая из этих строк заканчивается числом -2. В последней строке содержится число -1.
Выходные данные
Cтрока должна содержать количество "неизбежных" точек в заданном плане, после чего в той же строке должны следовать номера этих точек в любом порядке.
Изображения
 
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.11.2013, 09:50     Задача "Гонки по улицам" (обход ориентированного графа)
Посмотрите здесь:

C++ "Рекурсивная функция" (Обход бинарного дерева)
C++ Матрица/связные_списки смежности для ориентированного графа
C++ предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику
C++ Обход "End Of File". Работа с файлами
Построение ориентированного графа C++
C++ Добавить размеры в код "Обход конем"
Разница между понятиями "Обход в прямом направлении" и "Итерационный прямой обход" C++
Написать программу, выводящую список всех "циклических" вершин ориентированного графа C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
SatanaXIII
19.11.2013, 14:50     Задача "Гонки по улицам" (обход ориентированного графа)
  #2
 Комментарий модератора 
s2df, пункт 5.5 Правил: запрещено дублировать тему.
Yandex
Объявления
19.11.2013, 14:50     Задача "Гонки по улицам" (обход ориентированного графа)
Ответ Создать тему
Опции темы

Текущее время: 12:24. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru