Wataru

Та же ошибка, что и в прошлом вопросе. Вы в очередь в обходе вширину всегда кладете соседние вершины, а надо это делать, только если они не помечены.

Вы там еще очередь pop-аете раньше времени.

В BFS вы не проверяете, что вершина помечена, и всегда кладете вершину в очередь. А еще там в конце какой-то левый цикл ненужный. Поиск бесконечно циклится и съедает всю память. DFS, похоже, правильный (есть много претензий к стилю, правда).

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

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

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

Но это все равно будет работать за экспоненциальную сложность.

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

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

Эйлеров путь существует от вершины с выходной степенью на 1 больше входной степени до вершины у которой входная степень на 1 больше, чем выходная. (Если граф неориентированный, то путь от одной нечетной вершины до другой). При этом все остальные вершины должны быть сбалансированны.

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

Соответственно, вам надо подсчитать степени всех вершин, проверить что все хорошо (максимум одна с in==out+1 и одна с in==out-1) и запустить или от любой или от той, у которой исходящих ребер больше.

Попробуйте переписать с массивами фиксированной длины. Во всех реализациях по вашим ссылкам вершины нумеруются строками и куча массивов типа distance и visited на самом деле являются словарями, или как это в js называется. Это работает сильно медленнее тупого массива, пронумерованного от 0 до n.

Вам понадобится один словарь для перенумерации вершин в числа. Потом преобразуйте гарф на массив массивов, вместо этого сложного объекта.

И уже на нем гоняйте дейкстру. Должно по карйней мере в пару раз ускорится. А то и во все 10.

Вам просто надо пересечь 3 окружности на плоскости. По "формула пересечения окружностей" гуглится, например, это или это.

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

Если боты должны обходить полигоны на каком-то расстоянии (не могут их касаться, как у вас на картинке), то раздуйте все полигоны на этот радиус (для каждой вершины найдите 2 внешние нормали к соседним сторонам, сдвиньте стороны на r вдоль этих нормалей и пересеките). Можно вывести формулу на бумажке через косинусы/синусы между нормалями (т.е. векторное/скалярное произведения нормалей). Надо будет к точке прибавить обе нормали, умноженные на 1/(cos(a/2)*sqrt(2+2cos(a))), где a - угол между нормалями.

Теперь можно считать ботов точками и они могут касаться полигонов.

Постройте граф. Вершины в графе - вершины полигонов, боты и игрок. Для каждой вершины и другого полигона найдите 2 касательные с точки на полигон - можно перебрать все отрезки из вершины на другой полигон и отбросить те, относительно которых 2 стороны второго многоугольника лежат по разные стороны. Также все эти касательные проверьте на пересечение со всеми остальными полигонами и удалите те, которые пересекаются (проверьте каждую сторону полигона, и пересеките сторону с известным отрезком-касательной).

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

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

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

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

Теперь - пересчет при движении игрока. Переодически надо пересчитывать пути для ботов. Для этого надо перестроить касательные от игрока и ботов на полигоны и снова прогнать Дейкстру.

Теперь про скорость. Можно делать просто, как я описал выше. Все что надо - это уметь проверять, что 2 отрезка пересекаются, и что полигон лежит по одну сторону от луча. Ну и алгоритм Дейкстры.

Касательные между препятствиями вы строите только один раз, тут скорость не так важна. Хуже с точками ботами и игроком. Тут касательные надо искать часто. Если полигоны очень большие, то можно искать точки пересечения и касательные за логарифм, но это очень заумные алгоритмы, через троичный поиск. Могу потом написать, если надо.

Самое медленное, это для каждой касательной проверять на пересечения со всеми полигонами (это n^2 проверок, если у вас n полигонов). Тут можно тоже очень хитро ускорить до n log n проверок, если все касательные отсортировать по углу и потом сделать что-то вроде алгоритма заметающей прямой, но вращать ваш взгляд вокруг точки. Это совсем сложно даже описать, не говоря уж о реализации. Надо складывать полигоны в что-то вроде сбалансированного дерева поиска, которое будет поддерживать их в отсортированном порядке относительно расстояния до точки. Каждая касательная или добавляет полигон, или удаляет его. Вы добавляете касательную только если при добавлении или удалении полигона он был самым ближайшим. Тут нужно будет уметь определять расстояние от точки до полигона вдоль прямой. Опять же, можно сделать тернарным поиском по точкам полигона.

Еще есть вариант через BSP (как в Думe. Дейстивительно эта задача, фактически, узнать, какие полигоны видны из любой точки. Очень близкро к компьютерной графике). Надо разбить всю плоскость на области и для каждой области хранить, на какие полигоны есть касательные из нее. Для этого надо все стороны полигонов продлить до прямых. Все со всем персечь, выделить области. Потом для любой точки в каждой области построить касательные и сохранить. Потом все эти области объеденить в BSP. Это очень хорошее ускорение, но оно работет только если у вас карта статичная. Можно предподсчитать и записывать в файл уже BSP.

Поиск пути в графе тоже можно подускорить. Без добавления ботов и игрока в граф найдите все кратчайшие пути методом Флойда. Теперь, когда вы построили все касательные, для каждого бота переберите касательную его и касательную из игрока. Вы можете моментально подсчитать кратчайший путь через эти касательные, ведь часть пути внутри графа на полигонах уже предподсчитана из алгоритма Флойда. Это будет заметно быстрее, чем гнать дейкстру каждый раз, ибо касательныйх сильно меньше, чем вершин всего в графе.

Один момент меня смущает: зачем вы внутри DFS не вызываете cycle когда у вас есть ребро в p? Это цикл длины 2 - вполне нормальный цикл. Или по условию задачи такие надо исключить?

А главная ошибка - надо при выходе из dfs помечать вершину другим цветом - как обработанную (например, 2). Чтобы color == 1 только у вершин, которые в стеке. При этом в самом Dfs нужно рекурсивно вызываться только отвершин с color == 0.

Допустим, у вас в графе есть ребро 2->1 и все. Вы вызоветесь от вершины 1 в цикле в main, ничего не найдете. Потом вызоветесь от вершины 2, найдете ребро в уже обработанную вершину и среагируете на это, как на цикл. Хотя это не цикл.

Да, могут быть нужны. Про то, что ограничения порядка 10^5 - это не факт. Может быть и задача, где ограничения меньше, а решение сложнее.

Потом, еще важные алгоритмы - максимальное паросочетание, максимальный поток и максимальный поток минимальной стоимости (в порядке увеличения сложности и уменьшения частоты).

Далее, что за дерево отрезков на графе?! А еще дейкстра может быть написан за (n+m)logn. И форд-беллман работает за nm, а не n^2.

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

Раздуйте граф, сделав копии каждой вершины для каждого возможного времени. Т.е.если предполагается, что есть решение не длинее 1000 едениц веремни, то создаете граф с 1000*V вершинами, по одной для каждой вершины начального графа и возможного времени. Для каждого ребра входного графа u->v создайте ребро {u,t}->{u,t+1}. В этом графе есть много входных вершин (любое время, начальная вершина) и много конечных вершин (любое время). Но тут уже нет условия на непересечение машин в одно и то же время. Вместо этого пути машинок просто не могут пересекаться по вершинам вообще. Ведь каждая вершина символизирует вершину+время.

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

В этом графе пути уже должны не пересекаться по ребрам (ведь каждая вершина заменена ребром между двумя новыми вершинами) и все пути ведут из начала в конец. Чтобы разрешить машинам пересекаться в начальной и конечной вершине, начальные и конечные вершины графа не раздваивайте и сделайте пропускную способность ребер из начальной и в конечную вершины равными n. Все остальные пропускные способности равны 1.

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

Что бы найти оптимальный пути запустите бинарный поиск по ответу. Вот выбрали вы число 1000, создали искуственный граф со временем до 1000 для всех вершин. Запустили в нем максимальный поток. Если он нашел меньше n путей, то за 1000 едениц времени все n машин не пустить, пробуйте большее время. Если нашли хотя бы n путей, то можно взять любые n из них.

Изначальную верхнюю границу по времени можно взять n+V (V - путь в графе, и все машины идут по нему колонной одна за другой).

Возможно есть улучшение этого решения такое: Вместо бинарного поиска по ответу вы увеличиваете максимальное время на 1, добавляете новые вершины и ребра в граф и каждый раз ищете дополняющие пути (не отчищая уже найденый максимальный поток). Это рещение вроде будет побыстрее, но тут надо аккуратно понимать, что такое остаточная сеть.