Operations
(Mylib/Misc/rho.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00

Operations

Requirements

Notes

Problems

References

Code

#pragma once
#include <utility>
#include <vector>

template <typename F>
std::pair<int, int> rho(int N, int first, F f) {
  std::vector<int> check(N);

  int tail = 0, cycle = 0;
  int a = first, i = 1;
  while (true) {
    check[a] = i;

    a = f(a);
    ++i;
    if (check[a] > 0) {
      tail  = check[a] - 1;
      cycle = i - check[a];
      break;
    }
  }

  return {tail, cycle};
}

#line 2 "Mylib/Misc/rho.cpp"
#include <utility>
#include <vector>

template <typename F>
std::pair<int, int> rho(int N, int first, F f) {
  std::vector<int> check(N);

  int tail = 0, cycle = 0;
  int a = first, i = 1;
  while (true) {
    check[a] = i;

    a = f(a);
    ++i;
    if (check[a] > 0) {
      tail  = check[a] - 1;
      cycle = i - check[a];
      break;
    }
  }

  return {tail, cycle};
}

Back to top page