Тема: Количество достижимых вершин в DAG
Собственно, есть DAG, нужно для каждой вершины узнать сколько вершин достижимо из неё. Нужно самое быстрое решение. Слышал, можно как-то сделать за (N^2)/32, но слабо представляю как.
Re: Количество достижимых вершин в DAG
Можно флойдом за N^3/32
Re: Количество достижимых вершин в DAG
Хмм... А зачем, если можно уже дфсом за N^2? Я сейчас не говорю о полном графе, так как при больших N входные данные слишком уж большие.
Re: Количество достижимых вершин в DAG
Ну можно за MN/32. Это оно?
5 2011-11-25 15:32:36 Отредактировано coder.ua (2011-11-25 19:16:54)
Re: Количество достижимых вершин в DAG
Такое подходит. Можно поподробней?
Re: Количество достижимых вершин в DAG
Ладно, всем спасибо, сам уже понял решение за NM/32. А быстрее решений не существует?