haar_lib/algo/
cycle_finding.rs

1//! 循環検出法
2//!
3//! # References
4//! - <https://ja.wikipedia.org/wiki/%E3%83%95%E3%83%AD%E3%82%A4%E3%83%89%E3%81%AE%E5%BE%AA%E7%92%B0%E6%A4%9C%E5%87%BA%E6%B3%95>
5//!
6//! # Problems
7//! - <https://atcoder.jp/contests/abc179/tasks/abc179_e>
8//! - <https://atcoder.jp/contests/typical90/tasks/typical90_bf>
9
10/// [`cycle_finding`]の結果
11#[derive(Clone, Copy, Debug, PartialEq, Eq)]
12pub struct Rho {
13    /// 先頭の非循環部の長さ
14    pub tail: u64,
15    /// 循環部の長さ
16    pub cycle: u64,
17}
18
19/// 循環検出法
20///
21/// **Space complexity** $O(1)$
22pub fn cycle_finding<T>(init: T, f: impl Fn(T) -> T) -> Rho
23where
24    T: Copy + Eq,
25{
26    let mut a = init;
27    let mut b = init;
28    loop {
29        a = f(a);
30        b = f(f(b));
31
32        if a == b {
33            break;
34        }
35    }
36
37    let mut tail = 0;
38    let mut c = init;
39    while a != c {
40        c = f(c);
41        a = f(a);
42        tail += 1;
43    }
44
45    let mut cycle = 0;
46    loop {
47        a = f(a);
48        c = f(f(c));
49        cycle += 1;
50
51        if a == c {
52            break;
53        }
54    }
55
56    Rho { tail, cycle }
57}
haar_lib/algo/cycle_finding.rs

haar_lib/algo/
cycle_finding.rs
