Привет, аноны, я снова здесь, чтобы просить у вас помощи. Я уже две недели ебусь с задачей на графы. Десять дней назад я создавал тред, где анон написал, что нужно сделать граф блоков и точек сочленения. С точками сочленения проблем нет, но с блоками - это пиздец. В интернете тупо нету кода, который ищет их. Есть инструкции и объяснения. Я перепробовал их все, но они ТУПО НЕ РАБОТАЮТ. Просто блять не работают, я не знаю почему. Сделав 1 в 1 как в инструкции, я обнаруживаю какой-нибудь баг, потом исправляю его, появляются ещё и ещё, и я понимаю, что это не инструкция а хуета полная. Что это блять за инструкция, сделав которую, нихуя не работает??? Так вот, я прошу у вас хоть как-то помочь мне с кодом поиска блоков в графе. В идеале конечно, чтобы вы его написали, потому что я заебался по инструкциям работать, меня уже трясёт всего.Вот текст из прошлого треда:Есть тут аноны, разбирающиеся в графах? Есть задача, бьюсь над ней уже третий день. Мне дают неориентированный граф, не содержащий петель и кратных ребер. Также мне дают некоторое количество пар вершин. Мне нужно найти кол-во точек сочленения в диапазоне этих вершин, не считая начальной и конечной вершины.Вот строчка из оригинального текста(вы поймете, зачем я её вставил сюда): Для каждой описанной пары выведите на отдельной строке единственное число —- количество вершин c, таких, что любой путь из ai в bi, проходит через cПривожу пример:1. Мне даётся пкрл граф и одна пара(1, 5). Точки сочленения между этими вершинами - это 2 и 3, значит ответ - 2(две вершины).2. Тот же граф, но пара (9, 7). Программа должна вывести 0, т.к. нету такого пути из 9 в 7, чтобы он проходил постоянно по одной и той же вершине(точка сочленения есть, но вершины такой нет, так что можно сказать, что это частный случай).С нахождением точек сочленения проблем нет, но я не знаю, как вычленить из графа именно нужный мне путь. То что делается это всё поиском в глубину, я думаю, это ясно. Так вот если ввести 9 и 7, то поиск пойдёт от 1 до 6, посчитает точки сочленения, это (1, 2, 3), вернётся в единицу, пробежит 7, 8 и 9 и выдаст мне ответ 3, т. к. он пробежит весь граф, а мне нужен диапазон именно от 9 до 7, чтобы оно не ходило по лишним вершинам.К слову, подразумевается, что всё это можно сделать только поисками в глубину.
Буду бампать, пока не здохну, мне уже нечего терять.
Бамп
Бамп.
В матрицах смежности там все пральна считается ?
Ищешь тем же DFSом от 1 вершины, но как только доходишь до 2, стопаешься. Вроде всё.
>>149145191Да похуй на способ представления графа. Я использую матрицу, т к. там доступ к ребру О(1)
>>149145191Или это не задача коммивояжера, выкачусь пожалуй нахуй
>>149145339Ты хоть читал оп пост?
Бамп(((( сука((( в тот раз аноны умнее были((
Вбпмр
>>149145352Нет, не похуй. Матрица -- O(n^2), список смежности -- O(n+m), если нужен доступ к ребру за быстро, пишешь хэшсетом.
>>149145403Да, тебе нужно найти количество точек, разделяющих A и B в разные компоненты.
>>149145559В задаче максимум вершин 400, так что лишние операции, которые дает матрица незначительны. Я планировал часто обращаться к ребру, вот и сделал ее.
>>149145714Я полторы недели назад тоже так думал. Если путь просто проходит через точку сочленения - это совсем не значит, что это нужный мне путь
>>149145824Ладно, я проебался, сейчас ещё подумаю.
>>149146171Буду ждать
>>149143990 (OP)Я не понял в чем твоя проблема. Ищешь все пути из a в b(раз не сказано, что нужен кратчайший), если в одном из них есть номер, равный числу пройденных вершин, то его выводишь, иначе 0.Или я ебусь в глаза и не понял суть задачи.А вообще, дай ссылку на задачу.
>>149143990 (OP)Если я понял правильно, тебе надо1 Найти сильно связные компоненты (http://e-maxx.ru/algo/connected_components) . Таким образом ты разметишь вершины по компонентам2 Просто запускать dfs из вершины ai до bi и считать количество вершин на пути, которые лежат в разных компонентах связностиКажется, всё. Или я не понял условие
>>149146248http://informatics.mccme.ru/mod/statements/view.php?id=15342#1
>>149146322просто компоненты связности, это ж не орграфсамофикс
>>149146400А если у меня граф - это одна большая компонента связности?Мне нужны именно компоненты ДВУСВЯЗНОСТИ.
Я чёт нихуя не понял.Разве не получится:1) Найти все пути.2) Посмотреть, есть такие вершины, которые находятся в каждом пути.3) Посчитать их.Твоя описание задачи - какое-то кривое говно.
>>149146702джвачую
>>149146248>Ищешь все путиИ как я это реализую? Что принимать за путь? Путь, который отличается на одну вершины от другого - это новый путь?>в одном из них есть номер, равный числу пройденных вершинТут не понял, в пути есть номер, равный числу пройденных вершин?
>>149146702Я так тоже думал, но отмел этот вариант, уже не помню почему. Объясни, как я буду искать пути
>>149146963>Объясни, как я буду искать путиЯ не смогу тебе сейчас назвать какой-то супероптимальный алгоритм, так как ничего сложнее Дейкстры мне не приходилось реализовывать, но это можно сделать даже просто обходом в ширину/глубину, удаляя с конца вершины, которыми воспользовался или типа того.По-моему, это должно сработать. Проблема может только быть в том, что там сложность будет неебическая. А может и нет.
>>149147424Я вспомнил, как я делал. Первым дфсом я нашел путь к второй вершине, потом нашел точки сочленения. И начал по одной удалять точки сочленения, которые есть в этом пути, и, если я удалил точку и поиск в глубину не добрался до второй вершины, то эта точка - нужная мне вершина. Программа не уложиась в ограничение по времени.
>>149146859> И как я это реализую?Строишь дерево. глубиной в число вершин(больше нет нужды). Заканчиваешь ветку в случае, если пришел в b. Потом все ветки которые не заканчиваются b отсекаешь.
Вот пик к >>149147889
Ебаная макаба.Вот пик к >>149147889
>>149147771Вот, можешь как он делать. >>149147967Потом смотришь какие вершины одинаковые. Я почти уверен, что ты какое-то говно накодил просто.
>>149147967>>149147889>>149148074И как мне сделать, так чтобы оно могло несколько раз проходить через вершину 4? Просто массив used использовать не получиться, потому что, забраковав четвёрку, мы не сможем пройти как минимум один путь.
>>149148326Лол, да как угодно. Можешь свой класс реализовать, можешь массивами. Как тебе удобно.
>>149148687Я не про реализацию, а про идею. Я просто не могу догнать, что нужно сделать, чтобы он не ходил по одному и тому же пути. Первое решение, что приходит на ум - это массив used, где индексы - вершины, а true/false - посещена вершина или нет. Но если так сделать, то после прохода через четвёрку, она заблокируется, и тогда один из путей (1, 4, 5, 6, 7) или (1, 4, 6, 7) не будет пройден. Понимаю, что сейчас жёстко туплю, но у меня уже сил нету
>>149143990 (OP)Алгоритм Дейкстры же. Че ты как клоун.Например пара (1, 5):Для каждой точки ставишь минимальное количество шагов до точки 1(то до старта)7 - 1 шаг8 - 2 шага9 - 1 шаг2 - 1 шаг3 - 2 шага5 - 3 шага6 - 3 шага4 - 3 шагаДальше берешь конечную точку 5 и смотришь веса его соседей:3 - 2 шага6 - 3 шага4 - 3 шагаБерем минимальный из них и если он такой только один, то выводим его, иначе 0.Пример для (9,7)8 - 1 шаг1 - 1 шаг7 - 2шага....Смотрим соседей конечного узла (7):8 - 1 шаг1 - 1 шагПолучается есть два минимальных пути, значит выводим 0.Надеюсь понятно?
>>149149171Понятно. Выглядит безумно круто, даже настолько, что не верится, что это правда. Объясню почему: 1. Задача в разделе под названием "Поиск в глубину". Подразумевается, что она решается только поисками в глубину и его модификациями. 2. Ограничение на задаче 2 сек. Твой вариант слишком быстрый.Если он >>149147967 не объяснит мне, как делать его способом, то, скорее всего, буду пробовать твой.
бамп
>>149149590Да это и есть поиск в глубину. Просто надо ставить весь для каждой вершины при обходе. Если он и так меньше, то прерывать обход. Это и есть алгоритм Дейкстры.
>>149149792Я придумал котртест на твой пример.
>>149150035А что не так? Должно работать3 - 2 шага4 - 3 шага11 - 4 шагаМинимальный 2. Значит ответ 2.
>>149150131Чёрт, не заметил. Похоже ты прав. Тогда тут удобнее BFSом шаги выставлять, нет?
>>149150344Ну дейкстра вроде как в ширину обходит. Но ты можешь и в глубину сделать. По идее это медленее будет, но тоже уложится в 2 сек. Главное отсекать пути(если у точки меньше вес) и не попадать в циклы.
>>149150497>отсекать путиМожно тут объяснить? >не попадать в циклыНу тут же просто массив used, не?
>>149150831Если будешь делать в ширину, то все ок. Если в глубину, то может быть такая ситация :1->2->3->4->5->11->10у 11 будет 5 шагов, а у 10 6 шагов. Их нельзя помечать used, так как есть более короткий путь.С другой стороны ты можешь попасть на точку 11, для который уже стоит мин вес 4, а твой текущий вес для нее 6. Значит надо прерывать этот обход. Потому что все остальные пути будут только увеличиваться и точно не будут минимальными. Ну и в цикл можно попасть. Короче условие прерывания обхода вес ноды < текущего веса.
>>149151291Все, я понял. Спасибо большое. Может напишешь свое мыло, я тогда результат тебе отправлю, когда напишу, вдруг не пойдет решение?Если откажешься, я пойму
бмп(жду анона)
