Дан граф с циклами, построить без циклов Опции

[Somebody]

Помогите с этой задачей.

[trminator]

Создаешь новый граф без дуг, но с тем же количеством вершин. Затем добавляешь одну дугу, если она не создает цикл.

Как распознать цикл: завести массив Mark[1..кол-во вершин], это будет массив "меток" вершин.
1) Сначала Mark[i] = i для всех i от 1 до кол-ва вершин
2) Выбираем новое ребро в том случае, если "метки" вершин, которые оно соединяет, разные. Пусть они равны, например, k и m.
3) Теперь нужно заменить по всему массиву все встречающиеся в нем элементы равные k, на m. Можно переходить снова к шагу 2.
4) Закончить, когда весь массив Mark будет заполнен одинаковыми элементами

(подробнее, как искать циклы, можно посмотреть в книге Окулова, глава Алгоритмы на графах, раздел "Каркас минимального веса. Метод Краскала". Фактически тебе нужно построить этот каркас, но не обязательно минимального веса. Книгу можно скачать на http://pascal.net.ru)

[Somebody]

А исходника нету?

[trminator]

Кстати у тебя граф-то ориентированный? А то этот алгоритм вроде как для  неориентированного... хотя может, и пройдет... Исходника нет. читай Окулова - умный мужик.

А вообще на бумажке порисуй минут 15-20-30-90, алгоритм вроде простой, написАть не должно быть очень сложно.

[trminator]

Да, для ориентированного графа это не проходит. А у тебя какой?