16.3 Пути по функциям-переходам¶

Идея раздела¶

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

Такой граф удобно воспринимать не просто как граф, а как функцию перехода:

• для каждой вершины x задана вершина succ[x],
• из x мы обязаны перейти именно в succ[x].

Поэтому такие графы называют:

• successor graph — граф преемников,
• functional graph — функциональный граф.

Главный вопрос раздела:

Если мы стартуем из вершины x и сделаем k переходов вперёд, в какой вершине окажемся?

Это и есть запрос вида succ(x, k).

Что такое successor graph¶

В обычном ориентированном графе из вершины может выходить много рёбер. В successor graph — ровно одно.

Например, пусть задано:

• succ[1] = 3
• succ[2] = 5
• succ[3] = 7
• succ[4] = 6
• succ[5] = 2
• succ[6] = 2
• succ[7] = 1
• succ[8] = 6
• succ[9] = 3

Тогда из каждой вершины мы всегда знаем единственный следующий шаг.

Структура таких графов¶

У functional graph есть очень важное свойство:

Каждая компонента связности состоит из одного цикла и нескольких цепочек, которые в этот цикл ведут.

Почему так происходит:

1. Из каждой вершины есть ровно один выход.
2. Если идти достаточно долго, мы не можем бесконечно попадать только в новые вершины.
3. Значит, рано или поздно попадём в уже посещённую вершину.
4. С этого момента начинается цикл.

Иными словами, любая траектория в таком графе в конце концов «впадает» в цикл.

Наглядная схема¶

flowchart LR
    A1[1] --> A3[3]
    A3 --> A7[7]
    A7 --> A1

    A2[2] --> A5[5]
    A5 --> A2

    A4[4] --> A6[6]
    A6 --> A2

    A8[8] --> A6
    A9[9] --> A3

Здесь видно:

• цикл 1 -> 3 -> 7 -> 1,
• цикл 2 -> 5 -> 2,
• вершины 4, 6, 8 ведут в цикл 2 <-> 5,
• вершина 9 ведёт в цикл 1 -> 3 -> 7.

Запрос succ(x, k)¶

Обозначим через succ(x, k) вершину, в которой мы окажемся, если:

• стартуем в вершине x,
• сделаем ровно k переходов по рёбрам.

Примеры:

• succ(x, 0) = x, потому что без переходов мы остаёмся на месте;
• succ(x, 1) = succ[x];
• succ(x, 2) = succ[succ[x]].

Если считать «в лоб», то для каждого запроса нужно просто сделать k шагов. Это работает за O(k).

Но если:

• k очень велико,
• запросов много,
• k может быть порядка 10^9, 10^18 и больше,

то прямой проход слишком медленный.

Нужна идея ускорения.

Ускорение через степени двойки¶

Это один из самых полезных приёмов в графах и деревьях.

Вместо того чтобы хранить только непосредственного преемника, будем хранить:

• куда попадём через 2^0 = 1 шаг,
• куда попадём через 2^1 = 2 шага,
• куда попадём через 2^2 = 4 шага,
• куда попадём через 2^3 = 8 шагов,
• и так далее.

Обозначим:

• up[j][x] — вершина, в которую мы попадём из x через 2^j шагов.

Тогда:

• up[0][x] = succ[x]
• up[1][x] = succ(x, 2)
• up[2][x] = succ(x, 4)
• ...

Ключевая рекуррентная формула¶

Если мы умеем прыгать на 2^(j-1) шагов, то прыжок на 2^j шагов можно получить так:

up[j][x] = up[j-1][ up[j-1][x] ]

Смысл очень простой:

• сначала делаем 2^(j-1) шагов,
• приходим в какую-то вершину,
• потом ещё раз делаем 2^(j-1) шагов.

Итого получаем 2^j шагов.

Пример построения¶

Пусть:

• succ[1] = 3
• succ[3] = 7
• succ[7] = 1

Тогда:

• up[0][1] = 3
• up[0][3] = 7
• up[0][7] = 1

Теперь считаем переходы на 2 шага:

• up[1][1] = up[0][ up[0][1] ] = up[0][3] = 7
• up[1][3] = up[0][7] = 1
• up[1][7] = up[0][1] = 3

А на 4 шага:

• up[2][1] = up[1][ up[1][1] ] = up[1][7] = 3

То есть из вершины 1 за 4 шага мы попадём в 3.

Проверим вручную:

1 -> 3 -> 7 -> 1 -> 3

Всё верно.

Как отвечать на запросы¶

Теперь нужно научиться быстро вычислять succ(x, k).

Для этого раскладываем число k по степеням двойки.

Например:

• 13 = 8 + 4 + 1
• в двоичной записи это 1101

Значит, чтобы сделать 13 шагов, можно:

• сделать 8 шагов,
• потом 4 шага,
• потом 1 шаг.

Если бит j в числе k равен 1, то нужно применить переход up[j][x].

Пример¶

Если хотим найти succ(x, 13), то делаем:

• прыжок на 2^3 = 8 шагов,
• прыжок на 2^2 = 4 шага,
• прыжок на 2^0 = 1 шаг.

Именно это и даёт время O(log k) вместо O(k).

Почему это работает¶

Потому что любое натуральное число можно единственным образом представить как сумму степеней двойки.

Например:

• 11 = 8 + 2 + 1
• 19 = 16 + 2 + 1
• 37 = 32 + 4 + 1

Если для каждой степени двойки мы заранее знаем результат перехода, то длинный путь можно собрать из нескольких больших прыжков.

Их количество равно числу битов в k, то есть порядка log k.

Оценка сложности¶

Пусть:

• n — число вершин,
• U — максимальное число шагов, которое может встретиться в запросах.

Тогда:

Предобработка¶

Мы строим таблицу up[j][x] для всех:

• вершин x,
• уровней j, где 2^j <= U.

Это занимает:

• O(n log U) по времени,
• O(n log U) по памяти.

Один запрос¶

Чтобы вычислить succ(x, k), мы просматриваем биты числа k.

Это занимает:

• O(log k) времени.

Если запросов много, это даёт огромный выигрыш.

Код на C++¶

Ниже — базовая реализация для запросов вида: из вершины x сделать k переходов.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    const int LOG = 60;

    vector<vector<int>> up(LOG, vector<int>(n + 1));

    for (int i = 1; i <= n; i++) {
        cin >> up[0][i];
    }

    for (int j = 1; j < LOG; j++) {
        for (int i = 1; i <= n; i++) {
            up[j][i] = up[j - 1][up[j - 1][i]];
        }
    }

    while (q--) {
        int x;
        long long k;
        cin >> x >> k;

        for (int j = 0; j < LOG; j++) {
            if (k & (1LL << j)) {
                x = up[j][x];
            }
        }

        cout << x << '\n';
    }

    return 0;
}

Что делает этот код¶

1. Считывает граф¶

Мы предполагаем, что для каждой вершины i задан succ[i].

То есть вход хранит ровно один переход из каждой вершины.

2. Строит таблицу прыжков¶

up[j][i] — это вершина, куда попадём из i через 2^j шагов.

Сначала знаем переходы на 1 шаг. Потом строим переходы на 2, 4, 8, 16 и так далее.

3. Отвечает на запросы¶

Для каждого запроса разбираем число k по битам. Если очередной бит равен 1, делаем соответствующий прыжок.

Небольшой пример¶

Пусть дан граф:

• 1 -> 2
• 2 -> 3
• 3 -> 4
• 4 -> 5
• 5 -> 3

То есть есть цепочка, которая входит в цикл 3 -> 4 -> 5 -> 3.

flowchart LR
    A1[1] --> A2[2]
    A2 --> A3[3]
    A3 --> A4[4]
    A4 --> A5[5]
    A5 --> A3

Тогда:

• succ(1, 1) = 2
• succ(1, 2) = 3
• succ(1, 3) = 4
• succ(1, 4) = 5
• succ(1, 5) = 3
• succ(1, 6) = 4
• succ(1, 7) = 5

Видно, что после входа в цикл движение становится периодическим.

Очень важное наблюдение про циклы¶

В successor graph путь всегда устроен так:

1. сначала мы идём по цепочке,
2. потом попадаем в цикл,
3. дальше просто ходим по циклу.

Это означает, что в задачах часто полезно знать:

• расстояние до цикла,
• номер вершины в цикле,
• длину цикла.

Тогда можно отвечать не только на запросы про succ(x, k), но и на более сложные:

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

В самой основе всех таких задач лежит именно модель functional graph.

Практический пример задачи¶

Есть n телепортов. Для каждого города i задан город succ[i], куда телепорт переносит мгновенно. Нужно ответить на q запросов:

• стартуем из города x,
• используем телепорт ровно k раз,
• в каком городе окажемся?

Это классическая задача на successor paths.

Почему симуляция плоха¶

Если в каждом запросе честно делать k переходов, то при больших k решение будет слишком медленным.

Почему бинарное поднятие хорошо¶

Потому что вместо миллиарда шагов можно сделать около 30–60 прыжков по степеням двойки.

Ещё один пример кода: отдельная функция запроса¶

Иногда удобнее вынести вычисление в отдельную функцию.

#include <bits/stdc++.h>
using namespace std;

const int LOG = 60;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<vector<int>> up(LOG, vector<int>(n + 1));

    for (int i = 1; i <= n; i++) {
        cin >> up[0][i];
    }

    for (int j = 1; j < LOG; j++) {
        for (int i = 1; i <= n; i++) {
            up[j][i] = up[j - 1][up[j - 1][i]];
        }
    }

    auto jump = [&](int x, long long k) {
        for (int j = 0; j < LOG; j++) {
            if (k & (1LL << j)) {
                x = up[j][x];
            }
        }
        return x;
    };

    int q;
    cin >> q;
    while (q--) {
        int x;
        long long k;
        cin >> x >> k;
        cout << jump(x, k) << '\n';
    }

    return 0;
}

Типичные ошибки¶

1. Слишком маленький LOG¶

Если k может быть до 10^18, то LOG = 30 уже не хватит.

Безопасный вариант:

• LOG = 60 для long long.

2. Путаница с индексацией¶

Нужно заранее решить:

• вершины нумеруются с 0 или с 1,
• и везде придерживаться этого соглашения.

3. Неправильное построение таблицы¶

Формула должна быть именно такой:

up[j][i] = up[j - 1][ up[j - 1][i] ]

А не что-то похожее, но с перепутанными индексами.

4. Использование int для очень большого k¶

Если k большое, хранить его нужно в long long.

Где это применяется¶

Техника successor paths и бинарного поднятия встречается в задачах про:

• телепорты,
• перестановки и многократное применение перестановки,
• переходы по указателям,
• моделирование автоматов,
• поиск k-го предка в дереве,
• повторение операций много раз,
• циклы в функциональных графах.

На самом деле идея очень универсальна:

если есть операция «сделать один переход», то часто можно ускорить её многократное применение через прыжки по степеням двойки.

Связь с деревьями¶

Эта же идея позже появляется в задачах на деревья как binary lifting для поиска предков:

• up[0][v] — родитель вершины,
• up[1][v] — предок через 2 ребра,
• up[2][v] — предок через 4 ребра,
• и так далее.

То есть successor graph — очень удобное место, где эта техника объясняется в наиболее простом виде.

Итого¶

• В successor graph из каждой вершины выходит ровно одно ребро.
• Каждая компонента такого графа состоит из цикла и деревьев-путей, ведущих в него.
• Запрос succ(x, k) означает: куда попадём из x через k переходов.
• Наивное решение работает за O(k).
• Если заранее посчитать прыжки на степени двойки, можно отвечать за O(log k).
• Для этого используется таблица up[j][x].
• Основная формула: up[j][x] = up[j - 1][ up[j - 1][x] ].
• Это одна из самых полезных техник в олимпиадном программировании.

Что полезно потренировать после этого раздела¶

1. Реализовать запросы succ(x, k).
2. Научиться находить длину цикла, в который попадает вершина.
3. Научиться находить число шагов до входа в цикл.
4. Решить задачи на телепорты и функциональные графы.
5. Сравнить successor paths и binary lifting в деревьях.