Вроде можно решить , как задачу LCA . Этот алгоритм описан в e-maxx , но не очень хорошо понимаю, как это сделать.

Прочитав название темы, я подумал, что у тебя и у твоих родителей возникла проблема с какой-то задачей. Я один такой?

Прочитай эту тему про поиск в ширину а потом еще в глубину потом ты сможешь решать такие задачи

Поиск в ширину Поиск в ширину (обход в ширину, breadth-first search) — это один из основных алгоритмов на графах.

В результате поиска в ширину находится путь кратчайшей длины в невзвешенном графе, т.е. путь, содержащий наименьшее число рёбер.

Алгоритм работает за O (n+m), где n — число вершин, m — число рёбер.

Описание алгоритма На вход алгоритма подаётся заданный граф (невзвешенный), и номер стартовой вершины s. Граф может быть как ориентированным, так и неориентированным, для алгоритма это не важно.

Сам алгоритм можно понимать как процесс "поджигания" графа: на нулевом шаге поджигаем только вершину s. На каждом следующем шаге огонь с каждой уже горящей вершины перекидывается на всех её соседей; т.е. за одну итерацию алгоритма происходит расширение "кольца огня" в ширину на единицу (отсюда и название алгоритма).

Более строго это можно представить следующим образом. Создадим очередь q, в которую будут помещаться горящие вершины, а также заведём булевский массив \rm used[], в котором для каждой вершины будем отмечать, горит она уже или нет (или иными словами, была ли она посещена).

Изначально в очередь помещается только вершина s, и \rm used[s] = true, а для всех остальных вершин \rm used[] = false. Затем алгоритм представляет собой цикл: пока очередь не пуста, достать из её головы одну вершину, просмотреть все рёбра, исходящие из этой вершины, и если какие-то из просмотренных вершин ещё не горят, то поджечь их и поместить в конец очереди.

В итоге, когда очередь опустеет, обход в ширину обойдёт все достижимые из s вершины, причём до каждой дойдёт кратчайшим путём. Также можно посчитать длины кратчайших путей (для чего просто надо завести массив длин путей d[]), и компактно сохранить информацию, достаточную для восстановления всех этих кратчайших путей (для этого надо завести массив "предков" p[], в котором для каждой вершины хранить номер вершины, по которой мы попали в эту вершину).

Реализация Реализуем вышеописанный алгоритм на языке C++.

Входные данные:

vector < vector > g; // граф int n; // число вершин int s; // стартовая вершина (вершины везде нумеруются с нуля)

// чтение графа ... Сам обход:

queue q; q.push (s); vector used (n); vector d (n), p (n); used[s] = true; p[s] = -1; while (!q.empty()) { int v = q.front(); q.pop(); for (size_t i=0; i<g[v].size(); ++i) { int to = g[v][i]; if (!used[to]) { used[to] = true; q.push (to); d[to] = d[v] + 1; p[to] = v; } } } Если теперь надо восстановить и вывести кратчайший путь до какой-то вершины \rm to, это можно сделать следующим образом:

if (!used[to]) cout << "No path!"; else { vector path; for (int v=to; v!=-1; v=p[v]) path.push_back (v); reverse (path.begin(), path.end()); cout << "Path: "; for (size_t i=0; i<path.size(); ++i) cout << path[i] + 1 << " "; } Приложения алгоритма Поиск кратчайшего пути в невзвешенном графе. Поиск компонент связности в графе за O(n+m). Для этого мы просто запускаем обход в ширину от каждой вершины, за исключением вершин, оставшихся посещёнными (\rm used=true) после предыдущих запусков. Таким образом, мы выполняем обычный запуск в ширину от каждой вершины, но не обнуляем каждый раз массив \rm used[], за счёт чего мы каждый раз будем обходить новую компоненту связности, а суммарное время работы алгоритма составит по-прежнему O(n+m) (такие несколько запусков обхода на графе без обнуления массива \rm used называются серией обходов в ширину).

Нахождения решения какой-либо задачи (игры) с наименьшим числом ходов, если каждое состояние системы можно представить вершиной графа, а переходы из одного состояния в другое — рёбрами графа. Классический пример — игра, где робот двигается по полю, при этом он может передвигать ящики, находящиеся на этом же поле, и требуется за наименьшее число ходов передвинуть ящики в требуемые позиции. Решается это обходом в ширину по графу, где состоянием (вершиной) является набор координат: координаты робота, и координаты всех коробок.

Нахождение кратчайшего пути в 0-1-графе (т.е. графе взвешенном, но с весами равными только 0 либо 1): достаточно немного модифицировать поиск в ширину: если текущее ребро нулевого веса, и происходит улучшение расстояния до какой-то вершины, то эту вершину добавляем не в конец, а в начало очереди. Нахождение кратчайшего цикла в ориентированном невзвешенном графе: производим поиск в ширину из каждой вершины; как только в процессе обхода мы пытаемся пойти из текущей вершины по какому-то ребру в уже посещённую вершину, то это означает, что мы нашли кратчайший цикл, и останавливаем обход в ширину; среди всех таких найденных циклов (по одному от каждого запуска обхода) выбираем кратчайший. Найти все рёбра, лежащие на каком-либо кратчайшем пути между заданной парой вершин (a,b). Для этого надо запустить 2 поиска в ширину: из a, и из b. Обозначим через d_a[] массив кратчайших расстояний, полученный в результате первого обхода, а через d_b[] — в результате второго обхода. Теперь для любого ребра (u,v) легко проверить, лежит ли он на каком-либо кратчайшем пути: критерием будет условие d_a[u] + 1 + d_b[v] = d_a[b]. Найти все вершины, лежащие на каком-либо кратчайшем пути между заданной парой вершин (a,b). Для этого надо запустить 2 поиска в ширину: из a, и из b. Обозначим через d_a[] массив кратчайших расстояний, полученный в результате первого обхода, а через d_b[] — в результате второго обхода. Теперь для любой вершины v легко проверить, лежит ли он на каком-либо кратчайшем пути: критерием будет условие d_a[v] + d_b[v] = d_a[b]. Найти кратчайший чётный путь в графе (т.е. путь чётной длины). Для этого надо построить вспомогательный граф, вершинами которого будут состояния (v,c), где v — номер текущей вершины, c = 0 \ldots 1 — текущая чётность. Любое ребро (a,b) исходного графа в этом новом графе превратится в два ребра ((u,0),(v,1)) и ((u,1),(v,0)). После этого на этом графе надо обходом в ширину найти кратчайший путь из стартовой вершины в конечную, с чётностью, равной 0.

Поиск в глубину Это один из основных алгоритмов на графах.

В результате поиска в глубину находится лексикографически первый путь в графе.

Алгоритм работает за O (N+M).

Применения алгоритма Поиск любого пути в графе. Поиск лексикографически первого пути в графе. Проверка, является ли одна вершина дерева предком другой: В начале и конце итерации поиска в глубину будет запоминать "время" захода и выхода в каждой вершине. Теперь за O(1) можно найти ответ: вершина i является предком вершины j тогда и только тогда, когда starti < startj и endi > endj. Задача LCA (наименьший общий предок). Топологическая сортировка: Запускаем серию поисков в глубину, чтобы обойти все вершины графа. Отсортируем вершины по времени выхода по убыванию — это и будет ответом. Проверка графа на ацикличность и нахождение цикла Поиск компонент сильной связности: Сначала делаем топологическую сортировку, потом транспонируем граф и проводим снова серию поисков в глубину в порядке, определяемом топологической сортировкой. Каждое дерево поиска — сильносвязная компонента. Поиск мостов: Сначала превращаем граф в ориентированный, делая серию поисков в глубину, и ориентируя каждое ребро так, как мы пытались по нему пройти. Затем находим сильносвязные компоненты. Мостами являются те рёбра, концы которых принадлежат разным сильносвязным компонентам. Реализация vector < vector > g; // граф int n; // число вершин

vector color; // цвет вершины (0, 1, или 2)

vector time_in, time_out; // "времена" захода и выхода из вершины int dfs_timer = 0; // "таймер" для определения времён

void dfs (int v) { time_in[v] = dfs_timer++; color[v] = 1; for (vector::iterator i=g[v].begin(); i!=g[v].end(); ++i) if (color[*i] == 0) dfs (*i); color[v] = 2; time_out[v] = dfs_timer++; } Это наиболее общий код. Во многих случаях времена захода и выхода из вершины не важны, так же как и не важны цвета вершин (но тогда надо будет ввести аналогичный по смыслу булевский массив used). Вот наиболее простая реализация:

vector < vector > g; // граф int n; // число вершин

vector used;

void dfs (int v) { used[v] = true; for (vector::iterator i=g[v].begin(); i!=g[v].end(); ++i) if (!used[*i]) dfs (*i); }

Сделаем обход в глубину следующим образом:

int time_in[100500], time_out[100500], timer = 0;

dfs(v):
  time_in[v] = timer
  timer += 1
  for u in sons(v):
    dfs(u)
  time_out[v] = timer
  timer += 1

Теперь заметим, что одна вершина является предком другой <=> у неё время захода (time_in) меньше, а время выхода (time_out) больше.