1 Тема от alexander

  • alexander
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-05-06
  • Сообщений: 7

Тема: Наименьший общий предок (как задать граф?)

код, который я здесь привожу - из 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 ?

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

2 Ответ от KADR

  • KADR
  • Участник
  • Неактивен
  • Откуда: Киев
  • Зарегистрирован: 2009-06-25
  • Сообщений: 231

Re: Наименьший общий предок (как задать граф?)

Я думаю нумерация вершин начинается с 0.
vector<int> это массив интов, который можно динамически расширять и сужать, а vector<vector<int> > это массив массивов интов, где каждый элемент это вектор и количество векторов можно менять.
Я так понял, граф задается в виде списка смежности. Т.е. i-й элемент вектора graph содержит список всех вершин, которые смежны с i.

3 Ответ от amateur Отредактировано amateur (2010-05-06 16:09:03)

  • amateur
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-06-12
  • Сообщений: 11

Re: Наименьший общий предок (как задать граф?)

typedef vector < vector<int> > graph; - создание динамического списка смежности (т.е. к примеру i-ый вектор хранит номера вершин смежных с i-ой вершиной)

4 Ответ от alexander

  • alexander
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-05-06
  • Сообщений: 7

Re: Наименьший общий предок (как задать граф?)

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

5 Ответ от KADR

  • KADR
  • Участник
  • Неактивен
  • Откуда: Киев
  • Зарегистрирован: 2009-06-25
  • Сообщений: 231

Re: Наименьший общий предок (как задать граф?)

Порядок не имеет значения. Все равно таким образом граф задается однозначно (с точностью до перенумерации ребер).

6 Ответ от coder.ua

  • coder.ua
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-03-06
  • Сообщений: 78

Re: Наименьший общий предок (как задать граф?)

Я как паскальщик на код даже не смотрю=)Может это и к лучшему..:)

7 Ответ от alexander

  • alexander
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-05-06
  • Сообщений: 7

Re: Наименьший общий предок (как задать граф?)

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

8 Ответ от brainail

  • brainail
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-06-22
  • Сообщений: 165

Re: Наименьший общий предок (как задать граф?)

alexander пишет:

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

Это массив векторов ^^
То есть мы с самого начала задаём сколько у нас будет строк, а в каждой строке уже хранится динамический свой вектор smile Я в си++ не разбераюся, но надеюсь ответил верно >__<

9 Ответ от alexander

  • alexander
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-05-06
  • Сообщений: 7

Re: Наименьший общий предок (как задать граф?)

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

10 Ответ от alexander

  • alexander
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-05-06
  • Сообщений: 7

Re: Наименьший общий предок (как задать граф?)

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

11 Ответ от alexander

  • alexander
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-05-06
  • Сообщений: 7

Re: Наименьший общий предок (как задать граф?)

alexander пишет:

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

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

12 Ответ от e-maxx

  • e-maxx
  • admin
  • Неактивен
  • Откуда: Саратов
  • Зарегистрирован: 2009-06-10
  • Сообщений: 360

Re: Наименьший общий предок (как задать граф?)

Да, v - корень дерева. Выбирать-то можно его произвольно, но ответ будет зависеть от него wink
curh = 0 надо передавать.

Потом надо вызвать build_lca. (Странно, что у меня dfs этот не вызывается автоматически внутри build smile ).

Затем уже можем использовать эту страшную машину функцией lca, работающей за O(1), но с уймой всяких операциях под этой константой big_smile

Сайтe-maxx