Народ помогите горю!!!!!!!
Кто-нибудь знает алгоритм поиска сильно связанных компонент графа за линейное время!!!!!??

За линейное...? Попробую поискать... А ты пока зайди на http://algolist.manual.ru
Может там найдешь...

Тут такое дело, может поможет кто? Решил сделать задачку, но ума видно нехватает:
"В некоторой стране есть развитая сеть железных дорог. С
доисторических времён и до нашего времени в стране непрерывно
происходят военные перевороты, из-за которых в системе
железнодорожного транспорта этой страны происходят непрерывные
изменения. Дело в том, что во время очередного переворота некоторые
дороги разрушаются из-за военных действий, а пока новый
правитель некоторое время находится у власти, он восстанавливает
часть дорог.

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

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

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

В первой строке входного файла находятся целые положительные
числа 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; //шаг создания
};

Тогда связи от каждого города можно разложить на дерево, но с ним я работать не умею.
Подскажите кто-нибудь!

А на чем должна біть написана программа? Какой компилятор используется?

В принципе мне важно разобраться в алгоритме поиска, а переделать могу и сам, но вообще я работаю на C++.

Цитата

А на чем должна бiть написана программа?

В принципе мне важно разобраться в алгоритме поиска, а переделать могу и сам, но вообще я работаю на C++.

Неудача вышла...

Задача подозрительно напоминает мне задачу с чемпионатов ACM. Подобная же, по крайней мере, постановка задачи... :-?

Статистика
Придумывал алгоритм - 5 минут.
Пытался сформулировать и записывал текст - 1 час.

Сначала определений несколько

Уникальный маршрут - путь, который удовлетворяет условиям Джа.

Способ представления уникального маршрута в программе - обычный список вида

Код

PPathEl = ^PathEl; PathEl = record  //Индекс города  Town : Integer;  RLink : PPathEl; end;

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

Существует массив, в котором хранятся ссылки на сами уникальные маршруты. Например

Код

Path = record  //Длина маршрута целиком  Length : Integer;  Link : PPathEl; end; RNet = array [1 .. 50000] of Path;

Ещё есть массив, в котором хранится степень инцедентности "вершин графа" (т.е. сколько дорог выходит из города)

Код

array [1 .. 500]

Что-то похожее на алгоритм:

Для каждой очередной строки (если добавление)

1. изменить массив степеней инцедентности соответствующим образом

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

3. обработать "концевые" города маршрутов и если найдутся те маршруты, которые можно соединить, то сделать это.

4. отсортировать массив маршрутов по убыванию длин.

5. самый первый и будет максимальной длины маршрутом.

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

P.S.
1. намешал паскалевский код с Object Pascal'евским кажется...

2. я не думал насчёт максимальной длины массива маршрутов. Но, как я себе представляю, он может быть и не из 50000 элементов. А элементов всего из 500

3. не стал писать производительность алгоритма (она очевидна) - лень. Алгоритм несложный и достаточно нересурсоёмкий. Я вижу, кстати, путь к его ускорению - займись на досуге, если захочешь

P.P.S. примерно ход мысли хоть понятен?

Это сообщение отредактировал(а) acp - 11.1.2004, 23:34

А обход вершин делать чем-то очень похожим на поиск в ширину. ИМХО

Цитата

P.P.S. примерно ход мысли хоть понятен?

Почитаю... Может разбирусь, я же проги делаю в Win API , а с графами никогда...

Цитата

Задача подозрительно напоминает мне задачу с чемпионатов...

Задача с какой-то олимпиады скачал, всеросийской что-ли, не помню.

А пока, спасибо - может будут вопросы

Цитата

я же проги делаю в Win API

А я на ассемблере под WinAPI, но это не помешает реализовать подобный алгоритм.
Массив - он везде массив.

Цитата

P.P.S. примерно ход мысли хоть понятен?

Нет, ничего не понял... Помоги еще раз: покажи всю программу.

Цитата

А я на ассемблере под WinAPI, но это не помешает реализовать подобный алгоритм. Массив - он везде массив.

Асм - значит профи, а я листинги перепечатываю .

Это сообщение отредактировал(а) Fixin - 13.1.2004, 19:33

Цитата

Помоги еще раз: покажи всю программу

В смысле?
Программы нет. Это же только наметки кода алгоритма были...

Ну тогда просто: "Спасибо", а то время потратили...