Задача
Инфраструктура космической галактики состоит из [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 |  |
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
#include <iostream> #include <vector> using namespace std; int inspect(int vertice, vector<int> graph[], bool visited[]); bool allVisited(bool visited[], int n); int firstNotVisited(bool visited[], int n); int main() { int n, m, a, b; cin >> n >> m; vector<int> graph[n] = {}; //Ввод данных, создание списка смежности графа for (int i = 0; i < m; i++) { cin >> a >> b; a--, b--; graph[a].push_back(b); graph[b].push_back(a); } //Поиск наиболее популярного узла (планеты) //Осуществляется с помощью Depth-first search, поочередно убирая каждый узел //и перемножая кол-во планет в получившихся подграфах графа int maxPop = 0, maxPlanets = 0; for (int i = 0; i < n; i++) { bool visited[n] = {}; //Отмечаем "убранный" узел как уже посещенный, чтобы не учитывать его при обходе visited[i] = true; vector<int> structures; //Рекурсивно проходим по всему графу, пока остаются не посещенные узлы //Кол-во итераций = кол-во подграфов while (!allVisited(visited, n)) structures.push_back(inspect(firstNotVisited(visited, n), graph, visited)); int pop = n - 1; //Изначальная популярность - кол-во других планет, т.к. перелет //между ними и убранной планетой уже не возможен for (int j = 0; j < structures.size() - 1; j++) for (int k = j + 1; k < structures.size(); k++) pop += structures[j] * structures[k]; //Поочередно перемножаем кол-во планет из каждого подграфа if (pop > maxPop) { maxPlanets = 1; maxPop = pop; } else if (pop == maxPop) maxPlanets++; } cout << maxPop << " " << maxPlanets; } bool allVisited(bool visited[], int n) { for (int i = 0; i < n; i++) if (!visited[i]) return false; return true; } int firstNotVisited(bool visited[], int n) { for (int i = 0; i < n; i++) if (!visited[i]) return i; return -1; } int inspect(int vertice, vector<int> graph[], bool visited[]) { //Рекурсивный метод обхода графа //Проходится по всем смежным узлам из списка смежности, пока не наткнется //на уже посещенный узел int cnt = 1; visited[vertice] = true; for (auto e: graph[vertice]) if (!visited[e]) cnt += inspect(e, graph, visited); return cnt; } |
Решение
Для начала представим полученный граф из планет в виде списка смежности (список, где каждой вершине соответствует список смежных ей других вершин). Так как нам надо получить значение наибольшей популярности, будем поочередно убирать (по сути заранее отмечать ее как посещенную) каждую из вершин и смотреть, между сколькими парами вершин нельзя составить маршрут. Для этого воспользуемся depth-first search. Его суть состоит в том, что мы берем любую вершину и начинаем рекурсивно проходить по всем ее соседям, а потом по их соседям и так далее. Каждую посещенную вершину мы отмечаем, чтобы при попадании на посещенную ранее вершину выйти из рекурсии. Таким образом, мы запускаем рекурсивную функцию пока остаются не посещенные вершины. В конце мы получим список связных подграфов и количество вершин в каждом из них. Чтобы получить популярность искомой вершины, мы суммируем кол-во остальных вершин (так как у них нет маршрута к убранной вершине) и поочередное произведение кол-ва вершин полученных подграфов.
— Что вы имеете в виду когда пишите «список структур графа». Если вводите свои термины, нужно их определять. «Структурой графа будем называть…».
— Вы использовали для решения задачи поиск в глубину (DFS) из нашей последней в этом семестре лекции. Почему этого нет в метках? Вроде это самое характерное для вашего решения. А делать его рекурсией или стеком уже детали. Хоть и важные.
— Как думаете, орфографическая ошибка в названии задачи сделана автором специально или мы можем ее исправить здесь? Он на что-то намекает или просто ошибся?
— Пожалуйста, сделайте знаки меньше либо равно такими, как в ваших учебниках.
— Не забывайте ставить пробелы между словами.
— Я, конечно зачту работу, но меня удивляет, что вы ничего не ответили ни на один из моих вопросов. Сочли их риторическими?
— Мы изучали язык DOT и научились генерировать изображения графов. У вас не возникло желания визуализировать тесты?
— Пожалуйста, не используйте символы кириллицы для постоянной ссылки (адреса) вашей статьи.
Извините, нет, вопросы риторическими не счел, просто исправил замечания и пошел дальше готовиться к алгебре)
Языком DOT визуализировал графы для себя на этапе отладки, чтобы понять некоторые моменты просчета количества путей, но о том, чтобы вставить в статью не думал.