e-olymp 7233. Путешествия в космосе

Задача

Инфраструктура космической галактики состоит из [latex]N[/latex] планет и [latex]M[/latex] прямых межпланетных маршрутов, каждый из которых связывает ровно две разные планеты. Расстояния в космосе достаточно большие, поэтому, если планеты не имеют прямого сообщения, то во время перелетов используют транзитные планеты.

Популярностью планеты [latex]k[/latex] будем считать количество пар различных планет [latex]i[/latex] и [latex]j[/latex], перелет между которыми возможен только при использовании планеты [latex]k[/latex] [latex] (i, j, k = 1..N)[/latex]. Для заданной системы космических сообщений найти значение максимальной популярности и количество планет, достигающих её.

Входные данные:

В первой строке натуральные числа [latex]N[/latex] и [latex]M[/latex] ([latex]1 \leqslant N \leqslant 1000[/latex], [latex]1 \leqslant M \leqslant 5000[/latex]). В следующих [latex]M[/latex] строках по два натуральных числа, описывающие маршрут между планетами [latex]i[/latex] и [latex]j[/latex] [latex](i, j, k = 1..N)[/latex].

Выходные данные:

Ответ к задаче.

Тесты

Входные данные Выходные данные Схема
1 4 4
1 2
1 3
1 4
2 3
5 1
2 14 14
1 2
2 3
2 4
3 5
1 6
6 7
7 8
8 6
1 9
9 10
10 11
9 12
1 13
13 14
75 1
3 4 4
1 2
2 3
3 4
4 1
3 4

Код

 

 

Решение

Для начала представим полученный граф из планет в виде списка смежности (список, где каждой вершине соответствует список смежных ей других вершин). Так как нам надо получить значение наибольшей популярности, будем поочередно убирать (по сути заранее отмечать ее как посещенную) каждую из вершин и смотреть, между сколькими парами вершин нельзя составить маршрут. Для этого воспользуемся depth-first search. Его суть состоит в том, что мы берем любую вершину и начинаем рекурсивно проходить по всем ее соседям, а потом по их соседям и так далее. Каждую посещенную вершину мы отмечаем, чтобы при попадании на посещенную ранее вершину выйти из рекурсии. Таким образом, мы запускаем рекурсивную функцию пока остаются не посещенные вершины. В конце мы получим список связных подграфов и количество вершин в каждом из них. Чтобы получить популярность искомой вершины, мы суммируем кол-во остальных вершин (так как у них нет маршрута к убранной вершине) и поочередное произведение кол-ва вершин полученных подграфов.

Ссылки

3 thoughts on “e-olymp 7233. Путешествия в космосе

  1. — Что вы имеете в виду когда пишите «список структур графа». Если вводите свои термины, нужно их определять. «Структурой графа будем называть…».
    — Вы использовали для решения задачи поиск в глубину (DFS) из нашей последней в этом семестре лекции. Почему этого нет в метках? Вроде это самое характерное для вашего решения. А делать его рекурсией или стеком уже детали. Хоть и важные.
    — Как думаете, орфографическая ошибка в названии задачи сделана автором специально или мы можем ее исправить здесь? Он на что-то намекает или просто ошибся?
    — Пожалуйста, сделайте знаки меньше либо равно такими, как в ваших учебниках.
    — Не забывайте ставить пробелы между словами.

  2. — Я, конечно зачту работу, но меня удивляет, что вы ничего не ответили ни на один из моих вопросов. Сочли их риторическими?
    — Мы изучали язык DOT и научились генерировать изображения графов. У вас не возникло желания визуализировать тесты?
    — Пожалуйста, не используйте символы кириллицы для постоянной ссылки (адреса) вашей статьи.

    • Извините, нет, вопросы риторическими не счел, просто исправил замечания и пошел дальше готовиться к алгебре)
      Языком DOT визуализировал графы для себя на этапе отладки, чтобы понять некоторые моменты просчета количества путей, но о том, чтобы вставить в статью не думал.

Добавить комментарий