1 Ответ от alexander

(11 ответов, оставленных в Algo)

alexander пишет:

Наименьший общий предок. Нахождение за O (1) с препроцессингом O (N) (алгоритм Фарах-Колтона и Бендера)  http://e-maxx.ru/algo/lca_linear   -  в этой программе в функции main надо 1м делом запустить  void dfs (int v, int curh) ?
где v - Это произовльно выбранный нами корень?  а какую величину задать curh?

Всмысле 1м делом - после того как зададим граф? способом "номер вершины - номера смежных с ней вершин"

Перейти к разделу: Algo

2 Ответ от alexander

(11 ответов, оставленных в Algo)

Наименьший общий предок. Нахождение за O (1) с препроцессингом O (N) (алгоритм Фарах-Колтона и Бендера)  http://e-maxx.ru/algo/lca_linear   -  в этой программе в функции main надо 1м делом запустить  void dfs (int v, int curh) ?
где v - Это произовльно выбранный нами корень?  а какую величину задать curh?

Перейти к разделу: Algo

3 Ответ от alexander

(11 ответов, оставленных в Algo)

ну да, я это и написал, массив из векторов. массив векторов.  Только при просмотре его содержимого в отладке - ерунда какая-то. что-то напутал где-то наверно:)

Перейти к разделу: Algo

4 Ответ от alexander

(11 ответов, оставленных в Algo)

А в http://e-maxx.ru/algo/lca_linear   -   vector<int> g[MAXN];   -    это что? - массив из MAXN векторов типа инт?
т.е. тоже самое, что  vector < vector<int> > graph, но с меньшей функциональностью?

Перейти к разделу: Algo

5 Ответ от alexander

(11 ответов, оставленных в Algo)

да, действительно, пожалуй так и есть. Осталось только выяснить, имеет ли значение порядок. Но это уже проще.
Спасибо!

Перейти к разделу: Algo

6 Тема от alexander

(11 ответов, оставленных в Algo)

код, который я здесь привожу - из http://e-maxx.ru/algo/lca

Вероятно мой вопрос наивен, но - как задаётся граф в этом алгоритме? Да и не только в этом.
typedef vector < vector<int> > graph; -  что это значит?
< vector<int> > - это вектор состоящий из номеров двух вершин в любом порядке?
тогда graph - вектор этих пар, стоящих в любом порядке?
откуда начинается нумерация вершин графа? i=0..n или i=1..n?

в программе написано - int n = (int) g.size(); т.е. если число вершин в дереве N, то n=N-1;
lca_h.resize (n); то есть размер вектора lca_h не больше N-1;
Но далее идёт обращение lca_h[v], как это возможно, если v может быть равен N ?

Заранее спасибо за ответ

Перейти к разделу: Algo