Задача о графах

[arseniiv]

Думаю о курсовой, в которой надо написать программу, решающую вот что:
Дан орграф с циклами (не говорилось, но, наверно, с орциклами). Надо узнать, есть ли в нём вершина, при удалении которой все циклы исчезнут.

Ничего особого о свойствах такой вершины я не придумал, поэтому решил просто найти все циклы и найти пересечение множеств их вершин. Если оно пустое, вершины такой, естественно, нет. Тогда нужно найти как-то все орциклы. Скажите, можно ли придумать что-то лучше перебора? При том раз это орграф, получается, для полноты нужно поперебирать, начиная с каждой вершины. Прав ли я?

[Zealint]

Так а в чем проблема? Берем ориентированный граф, у которого есть матрица смежности.
Удаляем по одной вершине и запускаем алгоритм Флойда-Уоршалла, который скажет нам, есть ли способ попасть из вершины в саму себя не более чем за $n$ шагов (где $n$ - число вершин в новом графе). Сложность данного подхода есть $O(n^4)$, всяко лучше, чем перебор.

[arseniiv]

Тогда можно использовать поиск в глубину не для нахождения всех циклов, чтобы потом их пересекать, как я собирался, а для проверки на цикличность вместо Флойда — Уоршалла как здесь. Щас попробую понять сложность поиска в глубину. Мне почему-то кажется, что она меньше $O(n^3)$!
Ну да, и вроде вообще $O(n)$. Ага, нет, если граф не сильно связный, то придётся запускать поиск до $O(n)$ раз для всё ещё непосещённых вершин, к тому же, критерий цикла уже не работает. Да, в моём случае, наверно, ваш способ единственно возможный.

-- Вс окт 31, 2010 17:24:48 --

Не хочу трогать матрицу. Наверно, получится что-то типа этого:

for u in V   // этот цикл по убираемой вершине
    for k in V
        if k = u continue
        for i in V
            if i = u continue
            for j in V
                if j = u continue
                E[i, j] := E[i, j] || E[i, k] && E[k, j]
    Cyclic := false
    for i in V
        if E[i, i]
            Cyclic := true
            break
    if !Cyclic return true
return false

Ничего не упустил?

[Zealint]

Поиск в глубину работает за $O($число рёбер$)$. Это не всегда быстрее, чем Флойд, так как вы будете запускать поиск от каждой вершины.

То, что вы написали в коде - неправильно. Вместо

E[i, j] := E[i, j] || E[i, k] || E[k, j]

Должно быть хотя бы

E[i, j] := E[i, j] || E[i, k] && E[k, j]

А дальше не глядел... но там трудно вроде ошибиться.

[arseniiv]

Zealint в сообщении #368293 писал(а):

Должно быть хотя бы <…>

Исправил.