Перейти к содержанию

16.4 Обнаружение цикла

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

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

Идея задачи

Представим, что у нас есть ориентированный граф, в котором у каждой вершины есть ровно один следующий переход succ(v).

Если начать идти из некоторой стартовой вершины, то возможны две вещи:

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

Нас обычно интересуют два вопроса:

  1. Какая вершина является первой вершиной цикла?
  2. Какова длина цикла?

Пример

Рассмотрим такой граф преемников:

flowchart LR
    1 --> 2
    2 --> 3
    3 --> 4
    4 --> 5
    5 --> 6
    6 --> 4
Hold "Ctrl" to enable pan & zoom

Если стартовать из вершины 1, путь будет таким:

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 4 -> 5 -> 6 -> ...

Отсюда видно, что:

  • первая вершина цикла — 4;
  • длина цикла — 3;
  • сам цикл: 4 -> 5 -> 6 -> 4.

Простое решение

Самый очевидный способ — идти по вершинам и хранить все посещённые вершины.

Как только мы попали в вершину второй раз, можно сказать, что мы вошли в цикл.

Плюсы

  • очень легко реализовать;
  • хорошо подходит, если память не ограничена.

Минусы

  • требует O(n) дополнительной памяти.

Во многих задачах этого достаточно. Но есть более красивый подход, который работает за ту же асимптотику по времени, но использует только O(1) памяти.

Алгоритм Флойда

Этот метод также называют:

  • алгоритм черепахи и зайца;
  • Floyd cycle finding algorithm.

Идея очень простая:

  • один указатель двигается по одному шагу;
  • второй — по два шага.

Если цикл существует, то внутри цикла быстрый указатель обязательно догонит медленный.

Почему два указателя встретятся

Пусть:

  • до цикла нужно пройти mu шагов;
  • длина цикла равна lambda.

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

Так как один движется на 1 шаг, а другой на 2 шага, расстояние между ними меняется на 1 каждый ход. Значит, рано или поздно это расстояние станет равно нулю, и указатели встретятся.

Это ключевая идея всего алгоритма.

Шаг 1. Найти точку встречи внутри цикла

Запускаем два указателя:

  • slow = succ(x)
  • fast = succ(succ(x))

Дальше делаем:

  • slow идёт на 1 шаг;
  • fast идёт на 2 шага.

Пока они не совпадут.

Иллюстрация

Для графа выше при старте из 1 движение может выглядеть так:

Ход slow fast
старт 2 3
1 3 5
2 4 4

Они встретились в вершине 4.

Важно понимать: это не всегда начало цикла. Это просто некоторая вершина внутри цикла.

Шаг 2. Найти первую вершину цикла

Теперь один указатель ставим обратно в стартовую вершину x, а второй оставляем в точке встречи.

После этого двигаем оба указателя по одному шагу.

Первая вершина, в которой они встретятся, и будет началом цикла.

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

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

Это один из самых красивых фактов в теории алгоритма Флойда.

Для нашего примера

После первой встречи в вершине 4:

  • ставим slow = 1;
  • fast = 4.

Двигаем по одному шагу:

Ход slow fast
старт 1 4
1 2 5
2 3 6
3 4 4

Значит, первая вершина цикла — 4.

Шаг 3. Найти длину цикла

Когда мы уже знаем первую вершину цикла, длину можно найти очень просто:

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

Для нашего примера:

4 -> 5 -> 6 -> 4

Длина цикла равна 3.

Полный алгоритм

Вход

  • стартовая вершина x;
  • функция succ(v), которая возвращает следующую вершину.

Выход

  • first — первая вершина цикла;
  • length — длина цикла.

Сложность

  • время: O(n);
  • память: O(1).

Это и есть главное достоинство метода.

Код на C++

Ниже — удобная реализация в стиле олимпиадного программирования.

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

pair<int,int> floyd_cycle(int start, const vector<int>& succ) {
    int slow = succ[start];
    int fast = succ[succ[start]];

    while (slow != fast) {
        slow = succ[slow];
        fast = succ[succ[fast]];
    }

    slow = start;
    while (slow != fast) {
        slow = succ[slow];
        fast = succ[fast];
    }

    int first = slow;

    int length = 1;
    fast = succ[first];
    while (fast != first) {
        fast = succ[fast];
        length++;
    }

    return {first, length};
}

int main() {
    vector<int> succ = {
        0,
        2,
        3,
        4,
        5,
        6,
        4
    };

    int start = 1;
    auto res = floyd_cycle(start, succ);

    cout << "Первая вершина цикла: " << res.first << "\n";
    cout << "Длина цикла: " << res.second << "\n";

    return 0;
}

В этом примере:

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

Программа выведет:

  • первая вершина цикла: 4
  • длина цикла: 3

Более наглядная версия с восстановлением самого цикла

Иногда в задаче нужно не только найти начало и длину, но и вывести вершины цикла.

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

struct CycleInfo {
    int first;
    int length;
    vector<int> cycle;
};

CycleInfo find_cycle(int start, const vector<int>& succ) {
    int slow = succ[start];
    int fast = succ[succ[start]];

    while (slow != fast) {
        slow = succ[slow];
        fast = succ[succ[fast]];
    }

    slow = start;
    while (slow != fast) {
        slow = succ[slow];
        fast = succ[fast];
    }

    int first = slow;

    vector<int> cycle;
    cycle.push_back(first);
    int v = succ[first];
    while (v != first) {
        cycle.push_back(v);
        v = succ[v];
    }

    return {first, (int)cycle.size(), cycle};
}

int main() {
    vector<int> succ = {
        0,
        2,
        3,
        4,
        5,
        6,
        4
    };

    auto ans = find_cycle(1, succ);

    cout << "Начало цикла: " << ans.first << "\n";
    cout << "Длина цикла: " << ans.length << "\n";
    cout << "Вершины цикла: ";
    for (int x : ans.cycle) cout << x << ' ';
    cout << "\n";

    return 0;
}

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

Алгоритм Флойда полезен не только в задачах про графы.

1. Функциональные графы

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

2. Поиск цикла в последовательности

Если последовательность задаётся формулой вида

x_(i+1) = f(x_i)

то можно рассматривать значения как вершины, а переходы — как рёбра.

3. Задачи с телепортами и порталами

Если из каждой комнаты можно перейти только в одну следующую, это тоже граф преемников.

4. Работа со списками

Идея алгоритма Флойда известна также в задаче: есть ли цикл в односвязном списке.

Чем алгоритм Флойда лучше наивного подхода

Подход Время Память
Запоминать посещённые вершины O(n) O(n)
Алгоритм Флойда O(n) O(1)

Если память ограничена, выбор очевиден: алгоритм Флойда намного лучше.

Важные замечания

1. Метод работает именно для графа преемников

То есть у каждой вершины должен быть ровно один исходящий переход.

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

2. Точка первой встречи не обязана быть началом цикла

Это частая ошибка.

Сначала находится просто некоторая вершина внутри цикла. Только второй этап позволяет получить именно начало цикла.

3. Стартовая вершина может уже лежать в цикле

Тогда первая вершина цикла может совпасть со стартовой.

Например:

flowchart LR
    1 --> 2
    2 --> 3
    3 --> 1
Hold "Ctrl" to enable pan & zoom

Если стартовать из 1, то:

  • первая вершина цикла может быть 1;
  • длина цикла равна 3.

Небольшой дополнительный пример

Пусть переходы такие:

  • 1 -> 4
  • 4 -> 2
  • 2 -> 7
  • 7 -> 5
  • 5 -> 2

Тогда путь из 1 выглядит так:

1 -> 4 -> 2 -> 7 -> 5 -> 2 -> 7 -> 5 -> ...

Здесь:

  • первая вершина цикла — 2;
  • длина цикла — 3;
  • цикл: 2 -> 7 -> 5 -> 2.

Такой пример полезен, потому что первая встреча указателей вполне может случиться, например, в вершине 7, а не в 2.

Интуитивное резюме

Алгоритм Флойда стоит запомнить так:

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

Это один из классических алгоритмов, который часто появляется в олимпиадных задачах именно потому, что сочетает:

  • простую идею;
  • красивое доказательство;
  • очень сильную экономию памяти.

Что полезно запомнить

  • граф преемников = у каждой вершины один исходящий переход;
  • любой бесконечный проход по такому графу рано или поздно попадёт в цикл;
  • алгоритм Флойда находит цикл за O(n) времени и O(1) памяти;
  • после первой встречи указателей можно найти начало цикла;
  • затем легко найти и его длину.