10993. Сеть компании Bmail

Когда-то давно в небезызвестной компании Bmail был только один маршрутизатор. Шли года и с течением времени закупались новые маршрутизаторы. Каждый раз при покупке нового маршрутизатора он соединялся с одним из купленных до него. Вам заданы значения p_i – номер маршрутизатора к которому был подключен i-й после покупки (p_i < i).

Сейчас в Bmail всего n маршрутизаторов. Выведите последовательность маршрутизаторов на пути от первого до n-го.

Вход. В первой строке записано целое число n (2 ≤ n ≤ 200000) – количество маршрутизаторов. Далее во второй строке записано n – 1 целое число p₂, p₃, ..., p_n (1 ≤ p_i < i), где p_i равно номеру маршрутизатора, к которому подключили i-й после покупки.

Выход. Выведите путь от 1-го до n-го маршрутизатора. Путь должен начинаться с числа 1 и заканчиваться числом n. Все номера в пути должны быть различны.

Пример входа	Пример выхода
8 1 1 2 2 3 2 5	1 2 5 8

РЕШЕНИЕ

графы - поиск в глубину

Анализ алгоритма

Маршрутизаторы и их соединения образуют дерево. Следовательно путь от 1-го до n-го маршрутизатора определяется однозначно. Запустим поиск в глубину из вершины 1, поддерживая при этом массив предков: при движении по ребру u → v занесем pre[v] = u. Двигаясь по массиву предков мы сможем восстановить путь от вершины n до 1.

Пример

Рассмотрим как выглядит дерево из примера.

Путь от 1-го до 8-го маршрутизатора имеет вид: 1 → 2 → 5 → 8.

Реализация алгоритма

Объявим список смежности g для хранения графа. Объявим дополнительные массивы.

vector<vector<int> > g;

vector<int> pre, res;

Функция dfs совершает поиск в глубину из вершины v. Предком v при поиске в глубину является вершина p.

void dfs(int v, int p = -1)

{

Рассматриваем ребро графа v → to. Если to ≠ p, то устанавливаем pre[to] = v и запускаем поиск в глубину из вершины to.

for (int to : g[v])

if (to != p)

{

pre[to] = v;

dfs(to, v);

}

}

Основная часть программы. Читаем входные данные. Строим граф.

scanf("%d", &n);

g.resize(n + 1);

pre.resize(n + 1);

for (i = 2; i <= n; i++)

{

scanf("%d", &p);

Вершина p соединена с вершиной i. Ребра графа неориентированные.

g[p].push_back(i);

g[i].push_back(p);

}

Вызываем поиск в глубину из вершины 1.

dfs(1);

Восстанавливаем путь из n в 1 двигаясь по массиву предков.

for (i = n; i != 0; i = pre[i])

res.push_back(i);

Развернем путь чтобы он начинался с маршрутизатора 1 и заканчиваться маршрутизатором n.

reverse(res.begin(), res.end());

Выводим путь от 1-го до n-го маршрутизатора.

for (i = 0; i < res.size(); i++)

printf("%d ", res[i]);

printf("\n");