| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Задача на графах |
| Автор: shtasik 26.11.2003, 02:17 |
| Народ помогите горю!!!!!!! Кто-нибудь знает алгоритм поиска сильно связанных компонент графа за линейное время!!!!!?? |
| Автор: Fedor 27.11.2003, 09:36 |
| За линейное...? Попробую поискать... А ты пока зайди на http://algolist.manual.ru Может там найдешь... |
| Автор: Fixin 9.1.2004, 19:32 |
| Тут такое дело, может поможет кто? Решил сделать задачку, но ума видно нехватает: "В некоторой стране есть развитая сеть железных дорог. С доисторических времён и до нашего времени в стране непрерывно происходят военные перевороты, из-за которых в системе железнодорожного транспорта этой страны происходят непрерывные изменения. Дело в том, что во время очередного переворота некоторые дороги разрушаются из-за военных действий, а пока новый правитель некоторое время находится у власти, он восстанавливает часть дорог. Временами железнодорожная система в этой стране становилась довольно разветвленной, поэтому некоторые города могли быть соединены двумя и более дорогами. Кроме того, дорога могла начинаться и заканчиваться в одном и том же городе, причем для одного города таких дорог могло быть несколько. Инженер Джио проводит испытания новых сверхскоростных поездов. Поскольку поезда экспериментальные, у них не должно возникать трудностей при проезде через промежуточные города. Поэтому инженер Джио требует, чтобы ни в каком городе на пути поезда, кроме, может быть, начального и конечного, не было развилок. Точнее, из любого промежуточного города на пути поезда должны выходить либо ровно две дороги, ведущие в другие города (возможно, в один и тот же), либо ровно одна дорога, начинающаяся и заканчивающаяся в этом городе. Естественно, что Джио желает испытать поезд на максимальной возможной скорости, и поэтому после каждого изменения в системе путей он хочет знать максимальную длину пути, по которому может ехать поезд. Поскольку в доисторические времена не умели добывать железо, в начале никаких дорог между городами нет. В первой строке входного файла находятся целые положительные числа 1< n<500 - число городов в стране, и 1<m<50000 - число изменений в железнодорожной системе. В следующих m строках находится информация об изменениях состояния системы путей. Каждое изменение является либо добавлением дороги, либо удалением дороги. В случае добавления дороги в очередной строке записан ноль, а затем идут три целых числа. Первые два из них являются номерами городов, соединяемых дорогой, а последнее является длиной добавленной дороги. Города нумеруются целыми числам от 1 до n. Длина дороги является целым положительным числом, не превосходящим 10^6. В случае удаления дороги в очередной строке сначала записана единица, а затем идёт номер шага, на котором произошло добавление удаляемой дороги. Для каждого изменения системы путей выведите в очередную строку выходного файла символ `*', если после очередного изменения системы путей существует сколь угодно длинный путь, удовлетворяющий условиям, поставленным Джио. В противном случае выведите в выходной файл единственное целое число, являющееся длиной максимального возможного пути. Входнае данные: 5 16 0 2 3 4 0 3 4 3 0 1 2 1 0 5 5 4 1 1 1 4 0 4 1 4 0 4 5 1 0 1 4 1 1 7 0 1 5 7 1 2 1 3 1 8 1 9 1 11 Выходные: 4 7 8 * * 3 8 5 4 3 8 9 * 8 7 0 Я подумал, что можно-бы исполизовать как основной объект не вершину (город), а ребро (жд) и записывать все данные о связи в структуру: class tLink { private: int CitiA; int CitiB; int Len; int Stp; //шаг создания }; Тогда связи от каждого города можно разложить на дерево, но с ним я работать не умею. Подскажите кто-нибудь! |
| Автор: Fedor 9.1.2004, 22:14 |
| А на чем должна біть написана программа? Какой компилятор используется? |
| Автор: Fixin 10.1.2004, 21:45 |
| В принципе мне важно разобраться в алгоритме поиска, а переделать могу и сам, но вообще я работаю на C++. |
| Автор: Fixin 10.1.2004, 21:46 | ||
|
| Автор: Fixin 10.1.2004, 21:47 |
| Неудача вышла... |
| Автор: acp 11.1.2004, 23:15 | ||||||
| Задача подозрительно напоминает мне задачу с чемпионатов ACM. Подобная же, по крайней мере, постановка задачи... :-? Статистика Придумывал алгоритм - 5 минут. Пытался сформулировать и записывал текст - 1 час. Сначала определений несколько Уникальный маршрут - путь, который удовлетворяет условиям Джа. Способ представления уникального маршрута в программе - обычный список вида
Например, для двух городов, соединённых уникальным маршрутом, список будет иметь два элемента. Существует массив, в котором хранятся ссылки на сами уникальные маршруты. Например
Ещё есть массив, в котором хранится степень инцедентности "вершин графа" (т.е. сколько дорог выходит из города)
Что-то похожее на алгоритм: Для каждой очередной строки (если добавление) 1. изменить массив степеней инцедентности соответствующим образом 2. обработать все маршруты и искать в них соответствующие города - если город найден и степень инцедентности равна 2, то к данному маршруту приписывается этот путь и длина этого пути - если город найден и степень инцедентности больше 2-х, то данный маршрут перестаёт быть уникальным и его надо разбить на два маршрута - если город не найден (степень инцедентности изначально будет равна 0 или 1), то создаём новый уникальный маршрут 3. обработать "концевые" города маршрутов и если найдутся те маршруты, которые можно соединить, то сделать это. 4. отсортировать массив маршрутов по убыванию длин. 5. самый первый и будет максимальной длины маршрутом. Для каждой строки (если удаление) - обрабатывать почти также. P.S. 1. намешал паскалевский код с Object Pascal'евским кажется... 2. я не думал насчёт максимальной длины массива маршрутов. Но, как я себе представляю, он может быть и не из 50000 элементов. А элементов всего из 500 3. не стал писать производительность алгоритма (она очевидна) - лень. Алгоритм несложный и достаточно нересурсоёмкий. Я вижу, кстати, путь к его ускорению - займись на досуге, если захочешь P.P.S. примерно ход мысли хоть понятен? |
| Автор: Fedor 12.1.2004, 08:36 |
| А обход вершин делать чем-то очень похожим на поиск в ширину. ИМХО |
| Автор: Fixin 12.1.2004, 18:54 | ||||
Почитаю... Может разбирусь, я же проги делаю в Win API  , а с графами никогда... 
Задача с какой-то олимпиады скачал, всеросийской что-ли, не помню.  А пока, спасибо - может будут вопросы |
| Автор: acp 13.1.2004, 14:04 | ||
А я на ассемблере под WinAPI, но это не помешает реализовать подобный алгоритм. Массив - он везде массив. |
| Автор: Fixin 13.1.2004, 19:31 | ||||
Нет, ничего не понял... Помоги еще раз: покажи всю программу.
Асм - значит профи, а я листинги перепечатываю  . |
| Автор: acp 13.1.2004, 22:57 | ||
В смысле? Программы нет. Это же только наметки кода алгоритма были... |
| Автор: Fixin 14.1.2004, 20:01 |
| Ну тогда просто: "Спасибо", а то время потратили... |