Floyd's cycle-finding algorithm (tools/find_cycle.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2022-10-08 19:22:04+09:00
• Include: #include "tools/find_cycle.hpp"

template <typename T, typename F>
std::pair<long long, long long> find_cycle(T x0, F f);

It returns the minimum $(a, b)$ in lexicographical order such that $a \geq 0$, $b \geq 1$ and $f^a(x_0) = f^{a + b}(x_0)$.

Constraints

• $(a, b)$ such that $a \geq 0$, $b \geq 1$ and $f^a(x_0) = f^{a + b}(x_0)$ exists.

Time Complexity

• $O(a + b)$

License

• CC0

Author

• anqooqie

Required by

• Bell numbers (tools/bell.hpp)
• Berlekamp-Massey algorithm (tools/berlekamp_massey.hpp)
• Bostan-Mori algorithm (tools/bostan_mori.hpp)
• tools/detail/rolling_hash.hpp
• Precompute $n! \pmod{P}$ for $0 \leq n < P \approx 10^9$ (tools/large_fact_mod_cache.hpp)
• $\mathbb{Z} / (2^{61} - 1) \mathbb{Z}$ (tools/modint_for_rolling_hash.hpp)
• Polynomial (tools/polynomial.hpp)
• Polynomial interpolation (tools/polynomial_interpolation.hpp)
• Cache for $b^n \pmod{M}$ (tools/pow_mod_cache.hpp)
• Rolling hash (tools/rolling_hash.hpp)
• Signed Stirling numbers of the first kind (tools/stirling_1st.hpp)
• Stirling numbers of the second kind (tools/stirling_2nd.hpp)
• Twelvefold way (tools/twelvefold_way.hpp)

Verified with

• tests/bell/all.test.cpp
• tests/bell/consistent.test.cpp
• tests/bell/diagonal.test.cpp
• tests/bell/fixed_n.test.cpp
• tests/berlekamp_massey.test.cpp
• tests/bostan_mori.test.cpp
• tests/find_cycle.test.cpp
• tests/has_mod.test.cpp
• tests/large_fact_mod_cache/binomial.test.cpp
• tests/large_fact_mod_cache/fact.test.cpp
• tests/polynomial/multidimensional.test.cpp
• tests/polynomial/multipoint_evaluation.test.cpp
• tests/polynomial/multipoint_evaluation_other_mods.test.cpp
• tests/polynomial/naive_division.test.cpp
• tests/polynomial/ntt_division.test.cpp
• tests/polynomial/taylor_shift.test.cpp
• tests/polynomial_interpolation.test.cpp
• tests/polynomial_product.test.cpp
• tests/rolling_hash.test.cpp
• tests/stirling_1st/consistent.test.cpp
• tests/stirling_1st/fixed_k.test.cpp
• tests/stirling_1st/fixed_n.test.cpp
• tests/stirling_2nd/all.test.cpp
• tests/stirling_2nd/consistent.test.cpp
• tests/stirling_2nd/fixed_k.test.cpp
• tests/stirling_2nd/fixed_n.test.cpp
• tests/twelvefold_way/labeled_ball_labeled_box_at_least_1.test.cpp
• tests/twelvefold_way/labeled_ball_labeled_box_at_most_1.test.cpp
• tests/twelvefold_way/labeled_ball_labeled_box_unrestricted.test.cpp
• tests/twelvefold_way/labeled_ball_unlabeled_box_at_least_1.test.cpp
• tests/twelvefold_way/labeled_ball_unlabeled_box_at_most_1.test.cpp
• tests/twelvefold_way/labeled_ball_unlabeled_box_unrestricted.test.cpp
• tests/twelvefold_way/unlabeled_ball_labeled_box_at_least_1.test.cpp
• tests/twelvefold_way/unlabeled_ball_labeled_box_at_most_1.test.cpp
• tests/twelvefold_way/unlabeled_ball_labeled_box_unrestricted.test.cpp
• tests/twelvefold_way/unlabeled_ball_unlabeled_box_at_least_1.test.cpp
• tests/twelvefold_way/unlabeled_ball_unlabeled_box_at_most_1.test.cpp
• tests/twelvefold_way/unlabeled_ball_unlabeled_box_unrestricted.test.cpp

Code

#ifndef TOOLS_FIND_CYCLE_HPP
#define TOOLS_FIND_CYCLE_HPP

#include <utility>

namespace tools {

  template <typename T, typename F>
  ::std::pair<long long, long long> find_cycle(const T& seed, const F& f) {
    auto i = 1LL;
    auto j = 2LL;
    T x = f(seed);
    T y = f(f(seed));
    for (; x != y; ++i, j += 2, x = f(x), y = f(f(y)));

    i = 0;
    x = seed;
    for (; x != y; ++i, ++j, x = f(x), y = f(y));

    const auto head = i;

    ++i;
    j = i + 1;
    x = f(x);
    y = f(f(y));
    for (; x != y; ++i, j += 2, x = f(x), y = f(f(y)));

    const auto cycle = j - i;

    return ::std::make_pair(head, cycle);
  }
}

#endif

#line 1 "tools/find_cycle.hpp"



#include <utility>

namespace tools {

  template <typename T, typename F>
  ::std::pair<long long, long long> find_cycle(const T& seed, const F& f) {
    auto i = 1LL;
    auto j = 2LL;
    T x = f(seed);
    T y = f(f(seed));
    for (; x != y; ++i, j += 2, x = f(x), y = f(f(y)));

    i = 0;
    x = seed;
    for (; x != y; ++i, ++j, x = f(x), y = f(y));

    const auto head = i;

    ++i;
    j = i + 1;
    x = f(x);
    y = f(f(y));
    for (; x != y; ++i, j += 2, x = f(x), y = f(f(y)));

    const auto cycle = j - i;

    return ::std::make_pair(head, cycle);
  }
}

Back to top page