Wataru

Суть в том, что в графе нет одинаковых вершин или групп вершин. Их нельзя как-то переставить, что граф останется выглядеть точно так же. Вот пример граф из 4 вершин в виде квадрата. Его крутить можно как угодно и отражать - он выглядит точно так же - квадрат он и есть квадрат. А вот треугольник из одной вершины которого торчит путь длины 1, а из другой вершины - путь длины 2 - он несимметричный. Каждая вершина по своему уникальна. Одна вершина на треугольнике имеет степень 2. Одна имеет степень 3 и до ближайшей вершины-листа путь длины 1, Одна имеет степень 3 и до ближайшей вершины листа путь длины 2. Есть только одна вершина степени 2 не на цикле. Оставшиеся 2 вершины имеют степени 1, но от одной до цикла путь длины 1, а от другой - 2. Вы эти вершины как-то поменяйте местами и у вас граф будет выглядеть по другому.

Не обязательно все вершины должны иметь разную степень. Но их нельзя поменять местами, потому что они связаны с другими вершинам по разному.

Формула включения-исключения. Берете все графы, где хотя бы одна вершина соединена со всеми (их n*2^(n-2)*(n-1)), вычитаете все графы, где хотя бы две вершины соеденины со всеми (2 раза, ведь они 2 раза подсчитались), прибавляете графы, где хотя бы 3 вершины соеденины со всеми (3 раза)... И т.д.

Графов, где хотя бы k вершин имеют степень n-1 - C(n, k)*2^{(n-k-1)(n-k)/2}: тут можно выбрать k вершин и для каждого ребра из оставшихся n-k вершин есть 2 варианта - оно или есть, или нет.

Это будет за O(n log n) решение, если пердподсчитать все факториалы и обратные к им по модулю в задаче. Ну, или O(n^2), если считать сочетания через треугольник паскаля.

Ражеванное объяснение:

Сложно подсчитать количество графов где ровно 1 вершина такая полная. Но легко подсчитать те, где k или более таких. Мы их такие зафиксируем и нарисуем от них все ребра. А все оставшиеся ребра в графе могут быть любыми. Во-первых, можно выбрать эти k вершин - поэтому у нас есть множитель C[n,k]. Оставшиеся, незафиксированные ребра идут между любыми двумя оставшимся n-k вершин. Их (n-k)(n-k-1)/2. И каждое может быть или проведено или нет.

Поэтому всего таких графов, с не менее k вершин: F(k)=C[n,k]*2^{(n-k)(n-k-1)/2}.

Теперь, как подсчитать графы ровно с 1 вершиной? Можно взять F(1). Но мы насчитали много лишнего, Графы с 2мя такими вершинами мы в F(1) подсчитали 2 раза. Поэтому вычтем 2F(2). Теперь графы ровно с 3 вершинами мы подсчитали 3 раза в F(1) и 3 раза в каждом F(2). Поэтому пока мы их насчитали 3-2*3 = -3 раза. Поэтому прибавим 3F(3). И далее, получится, что графы ровно с 4-мя вершинами мы подсчитали 4 раза (4-2*6+3*4). И т.д.

Ошибка в том, что у вас граф криво задан. У вас там ровно 6 списков. А размер графа - 7. Поэтому в MakeStep вы обращаетесь к graph[6], а это undefined behavior. А там непонятно, что происходит. Может вы таблицу портите каким-то значениями и никогда положительного значения не получаете. Скорее всего корраптите память через обращение к мусорным adj в std::array (который на стеке лежит) и получаете мусор в каких-то локальных переменных.

Простой подход, если у вас есть выделенный лидер и по графу распространяется одна волна в каждый момент времени.

Лидер опрашивает остальные сервера по очереди (включая себя), и справшивает их, есть ли у них еще непокрашенные вершины. Если есть, инструктирует их запустить волну. Когда волна закончится, справшивает опять. Когда сервер говорит, что больше непокрашенных вершин нет - лидер переходит к следующему серверу.

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

Более сложный вариант - когда у вас сразу запускаются все волны. Опять же, без лидера совсем сложно будет.
Тут, наверно стоит сначала в каждом отдельном параграфе найти все компоненты связности отдельно. Это будут промежуточные варианты.

Потом каждый сервер по призрачным ребрам отсылает сообщение, какой номер имеет торчащая наружу компонента. Номера должны быть глобально уникальные. Например, можно в старших битах хранить номер сервера, а в младших локально уникальный номер.

Когда сервер получает сообщение о номере по призначному ребру, если этот номер меньше текущего у компоненты, она перекрашивается. И сообщение рассылается по всем остальным призрачным ребрам, торчащим из этой компоненты. Рано или поздно, все вершины одной компоненты по всем серверам будут помечены минимальным номером.

Чтобы определить, что все закончилось, можно разбить процесс на фазы. В первой фазе все рассылают свои номера. Во второй фазе только те, у кого номера обновились. И т.д. Фаза на сервере начинается после сообщения от лидера. Каждый сервер отправляет на лидер сообщение, когда он закончил рассылать свои номера и были ли там вообще обновления. Сообщения надо делать по tcp с подтверждением. Когда лидер заметит, что никто никаких сообщений больше не рассылал в предыдущей фазе - все сошлось.

Код вообще странно реализует поиск в ширину. Я уверен, что на каких-то тестах оно работать не будет. Зависит от порядка вершин в usersMap. Т.е. если вы их все переименуете, вы можете получить другой ответ.

Вообще тут не нужен обход в ширину, тут, кажется, достаточно цикла по всем вершинам.

А так ваш алгоритм зачем-то имеет внешний цикл по User user и если он натыкается на какую-то еще не посещенную вершину, то дальше уже перебирает все вершины в очереди и добавляет их соседей в очередь в цикле, фактически выполняя обход в ширину. Правда там в очереди будет лежать какая-то случайная вершина из цикла по user. Так что это будет обход вширину сразу из двух вершин.

На какой-то следующей итерации цикла он опять запустит обход в ширину от какой-то еще не посещенной вершины, если в графе несколько компонент связности. В итоге первый обход в ширину может затронуть одну или 2 компоненты связности, а все следующие обходы обойдут по одной компоненте.

Есть простой трюк сильно упростить задачу: Измените переходы из "конечной" вершины - она теперь с вероятностью 100% будет вести только в саму себя. Таким образом, процесс хотя бы раз достигший вершины, навсегда в ней останется.

А вопрос из задачи (если его понимать как: минимальное количество шагов, чтобы хотя бы раз посетить конечную вершину с вероятностью >99%) становится эквивалентен: минимальное количество шагов, чтобы быть в конечной вершине с вероятностью не меньше 99%.

А тут уже надо найти минимальное число k, такое что соответствующее значение в матрице A^k было бы > 0.99. A тут - это матрица переходов.

Можно или в тупую умножать матрицу саму на себя, пока значение в строке начальной вершины и столбце конечной вершины не станет достаточно большим. Это будет O(N^3*ответ). Или можно делать хитро: бинарным поиском перебирайте степень, а внутри логарифмическим возведением в степень считайте A^k. Это будет O(N^3*log(ответ)^2).

1) Можно представлять дерево всеми способами, как и граф. Но в этом случае о деревьях обычно и не говорят. Ну граф, ну без цикла может даже быть. Ну и что? Пользы никакой не несет. Вот если же дерево представлять подвешанным - с одним корнем, с детьми и родителем у каждой вершины, то уже есть куча полезных применений. В основном при реализации всяких хитрых структур данных.

2) Дерево представляется в виде массива. Но не любое. А только полу-полное двоичное дерево (у каждой вершины до 2 детей. Если ребенок один, то левый. Все уровни, кроме последнего заполненны целиком, последний заполнен слева-направо).

3) Дерево нельзя представить в виде списка в общем случае. Потому что список - линеен, а дерево нет. Можно детей в каждой вершине хранить списком. Ну или вырожденное дерево, где у каждой вершины есть только один ребенек.

4) Нет.

5) Нет.

Ориентированный граф, у которого все ребра идут парами туда и обратно, полностью соответсвует неориентированному графу. Но если хотя бы где-то нет обратной дуги (как на правой картинке), то это уже отличие.

Почему вообще придумали использовать ориентированне графы? Потому что они полезны. Например, отношение "любовь" между людьми можно описать ориентированным графом, а вот неориентированным - нет (ибо есть безответная любовь).

Иногда имеет смысл рассматривать неориентированный граф как оринетированный с парными дугами, если в процессе работы симетрия как-то нарушается. Например в алгоритмах поиска максимального потока на графе так и происходит. Поэтому он не работает с неориентированными графами - в них надо каждое ребро разбить на два туда и обратно.

Раз уж я в комментариях все разобрал, скопирую в ответ: куча мелких ошибок в коде, вроде:
- циклы с 1 вместо 0
- не инициализированные массивы
- опечатки

Самое простое - это сделать вершиной каждую клетку и гнать в этом графе поиск в ширину. Можно даже не строить граф явно - а просто при обходе смотреть на четырех соседей и проверять, а не стена ли там, а были ли мы в клетке (x+dx[k], y+dy[k]), и класть координаты в очередь, если надо.

Вы же хотите считать только перекрестки и повороты врешинами. В худшем случае, если поворотов в лабиринте много - это будет даже медленнее обхода в ширину. Потому что он работает за линию, а дейкстра - за O(n log n) в лучшем случае. Плюс там константа больше у этого n log n. Правда, это можно решить если вместо дейкстры использовать обобщенный 0-1-BFS (BFS с ограниченными ребрами - там где много очередей используется). Но реализация будет сильно посложнее простого BFS.

Но если так хотите - то делается это так: Сначала пройдитесь по всем клеткам и занумеруйте те, которые не являются коридором (один сосед, больше двух соседей, или соседи не вдоль одной прямой). Можно в отдельной матрице номера проставить.
Потом пройдитесь по каждому столбцу сверху вниз и по каждой строчке слева направо и храните последнюю встреченную вершину. Если встретили стену - забывайте про эту увиденную раньше врешину. Если встретили просто проход - пропускайте его. Если встретили поворот(вершину) - то создайте ребро между ней и последней увиденной (если она еще в памяти, ведь стена могла ее удалить). Ну и перепишите последнюю увиденную вершину.

Что-то типа такого:

int last_node = 0;
for (i = x_start, j = y_start; i <n && j < m; i+= dx, j+=dy) {
   if (is_wall[i][j]) {
    last_node = -1;
  }  
  if (node_number[i][j] <- 0) continue;
  if (last_node > 0) {
    // добавить ребро между вершинами.
    AddEdge(last_node, node_number[i][j]);
  }
  last_node = node_number[i][j];
}

Тут я просто добавляю ребра в строке или столбце между двумя соседними вершинами.

Надо или удалять из графа вершину, или помечать ее удаленной и в вашем алгоритме поиска пути просто пропускать такие помеченные вершины во всех циклах по вершинам.

а весом рёбер будет выступать расстояние между этими полями. для того чтобы после построения этого графа выбрать в нём 2 вершины и найти между ними кратчайший путь ... Двигаться по карте можно только по горизонтали и по вертикали.

Это какой-то бред. Начало фразы подразумевает, что ребра есть между всеми парами вершин, продолжение говорит, что все ребра длины 1 между соседними клетками. Я предполагаю что тут именно второй вариант.

Во-первых, занумеруйте все клетки. Подойдет простая формула вроде i+m*j

Вот у вас уже есть n*m вершин в графе. Теперь добавьте ребра. Для каждой клетки (два цикла) посмотрите 4 соседние клетки. Если обе клетки - ., то добавьте из текущей клетки ребро в соседнюю.

Соседей удобно перебирать, если завести константные массивы для смещений:

const int dx[4]= {1, 0, -1, 0};
const int dy[4]= {0, 1, 0, -1};

Тогда для клетки (i, j) можно перебрать всех соседей одним циклом на 4 итерации - (i+dx[k], j+dy[k]). Надо только не забыть проверить на выход за границы матрицы.

Ну и вам надо написать функцию типа AddEdge(int u, int v) которая будет в удобную для вас структуру данных добавлять ребра. Граф удобно хранить в виде списков смежности. На C++ это можно сделать просто std::vector<std::vector<int>> и добавлять соседей через vector::push_back. Это на практике работает быстрее всяких связных списков.

И у вас будет три вложенных цикла - внешние по всем клеткам, а внутренний по четырем направлениям. Внутри вы проверяете, что сосед по этому направлению есть и между клетками можно пройти. В этом случае вызывайте AddEdge.

А можно вообще граф не строить. Берете ваш алгоритм поиска кратчайшего пути (BFS, Dijkstra или A*) и там везде, где перебираются соседи одной вершины, вставляете код проверки четырех направлений через dx/dy. Вершины можно или нумеровать их координатами, и тогда все массивы пометок будут двумерными, или можно использовать формулу u = i+j*m, (i,j) = (u%m, u/m) для преобразования координат в номер вершины и назад.

А еще есть всякие алгоритмы, которые работают сильно быстрее за счет использования того факта, что у вас не произвольный граф, а сетка в матрице. Jump Point Search - один из таких алгоритмов. В нем граф умышленно не строится и работа идет непосредственно в матрице.

Что вы подразумеваете под словом "эффективный"?

Проблема в том, что циклов в графе из n вершин может быть O(n!) (n-факториал): представьте клику - граф, где есть ребра между всеми парами вершин. Любое подмножество вершин, да еще и в любом порядке, задает элементарный цикл.

Обычно под словом "эффективный" подразумевают полиномиальный алгоритм. Такой алгоритм тут, очевидно, не существует (потому что надо перебрать экспоненциальное количество объектов).

Используйте обход в глубину без запоминания обойденных вершин. Такой полный перебор гарантированно найдет все циклы. Можно его ускорить, если предварительно разбить граф на двусвязные компоненты мостами и искать циклы внутри каждой компоненты отдельно.