Day 155-Q3 | Floyd's Cycle Detection + Brent's Algorithm

問題

$N$ 頂点の functional graph（各頂点からちょうど1本の有向辺が出るグラフ。$f:\{0,\dots,N-1\}\to\{0,\dots,N-1\}$）と開始頂点 $x_0$ が与えられる。$x_0,f(x_0),f(f(x_0)),\dots$ という列はいずれ同じ頂点を繰り返す——このとき列の形は、尻尾（tail）の後にサイクル（cycle）が続く ρ（ロー）字型 になる。

尻尾の長さ $\mu$（最初にサイクルへ入るまでのステップ数）と、サイクルの長さ $\lambda$（サイクルを一周するのに必要なステップ数）を、訪問済み集合を持たない（メモリ$O(1)$の）アルゴリズムで求めよ。

入力形式

N x0
f_0 f_1 ... f_{N-1}

制約

$1\le N\le 10^6$

$0\le x_0,f_i\le N-1$

追加メモリは定数個の変数のみ（$O(N)$配列を新たに確保しない）

入出力例

入力例1

6 0
1 2 3 4 5 3

出力例1

3 3

$\mu=3,\lambda=3$。実際の列は $0\to1\to2\to3\to4\to5\to3\to4\to5\to\cdots$ で、$3,4,5$が周期3のサイクルを成す。

概念図：ρ（ロー）字型（入力例1）

ヒント（段階的開示）

ヒント1（方向性）

「訪れた頂点をsetに記録して重複を検出する」方法は$O(N)$の追加メモリを使ってしまう。今回はそれを禁止しているので、2つのポインタを異なる速度で進めるという発想が必要になる。1つは1歩ずつ（亀）、もう1つは2歩ずつ（うさぎ）進めると、両者はいずれ同じサイクル内の同じ頂点で出会う。

ヒント2（アプローチ）

Floyd's Tortoise and Hare: 亀を1歩、うさぎを2歩ずつ進め一致した時点で、亀を$x_0$に戻し両方1歩ずつ進めると$\mu$ステップ後に再び一致する（これが$\mu$）。一致点から片方だけ動かし戻ってくるまでの歩数が$\lambda$。Brent's Algorithmはうさぎだけを進め、歩数が2のべき乗を超えるたびに亀をうさぎの現在位置にジャンプさせ、より少ない関数呼び出し回数で同じ結果を得る。

ヒント3（誘導）

# Floyd:
# tortoise,hare = f(x0), f(f(x0))
# while tortoise!=hare: tortoise=f(tortoise); hare=f(f(hare))
# tortoise=x0
# while tortoise!=hare: tortoise=f(tortoise); hare=f(hare); mu+=1
# lam=1; hare=f(tortoise)
# while tortoise!=hare: hare=f(hare); lam+=1

# Brent:
# power=lam=1; tortoise=x0; hare=f(x0)
# while tortoise!=hare:
#     if power==lam: tortoise=hare; power*=2; lam=0
#     hare=f(hare); lam+=1

模範解答 (Python)

import sys

def solve():
    data = sys.stdin.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    x0 = int(data[idx]); idx += 1
    f = [int(data[idx + i]) for i in range(N)]

    def F(x):
        return f[x]

    # --- Brent's Algorithm（O(1)空間・関数呼び出し回数がFloydより少ない） ---
    power = lam = 1
    tortoise = x0
    hare = F(x0)
    while tortoise != hare:
        if power == lam:
            tortoise = hare
            power *= 2
            lam = 0
        hare = F(hare)
        lam += 1

    # mu の特定: hare を lam 歩進めた位置から、x0 と同時に1歩ずつ進めて再会するまで
    tortoise = hare = x0
    for _ in range(lam):
        hare = F(hare)
    mu = 0
    while tortoise != hare:
        tortoise = F(tortoise)
        hare = F(hare)
        mu += 1

    print(mu, lam)

solve()

Step-by-Step 解説

1なぜ「1歩ずつ」と「2歩ずつ」で必ず出会うか
サイクルに入った後、亀とうさぎの位置の差はうさぎが1歩多く進むたびに1ずつ増える(mod λ)。差は$0,1,\dots,\lambda-1,0,\dots$と巡回するので必ず差が0に戻る瞬間が来る——$O(N)$の訪問済み集合なしで閉路を検出できる。

2実測（N=6, x0=0, f=[1,2,3,4,5,3]）
ブルートフォースで正解確認: 列は0,1,2,3,4,5の後3に戻る。よって$\mu=3,\lambda=3$（サイクルは3→4→5→3）。

3Floyd vs Brentの関数呼び出し回数（実測）
両アルゴリズムをPythonで実際に走らせ比較した結果、Floydは17回、Brentは15回。この小さな例では差はわずかであり「Brentの方が定数倍速い」という主張をこの1例だけから一般化するのは早計である。Brentの理論的優位性はサイクル長λが大きいほど効いてくる漸近的な性質であり、λ~10^4規模での追加実験はしていない。

4μの特定方法の違い
Floydは「合流点を見つけた後、亀をx0に戻し両方1歩ずつ進める」。Brentは「確定したλの分だけ先に進めたポインタとx0を同時に1歩ずつ進める」。どちらも「λの倍数だけ先を歩くポインタと合流するまでの歩数がμに等しい」という同じ原理に基づく。

よくあるミス

ミス	原因	正しい書き方
サイクル検出フェーズの合流点をそのままμだと思う	Floyd1段階目の合流点はサイクル内のどこかで尻尾の終端とは限らない	合流点発見後、必ず第2フェーズでμを再計算する
Brentでpowerとlamの更新順序を間違える	判定をhare更新の後に行うと1回分ずれる	判定→(必要なら)tortoise更新とpower倍化→hareを1歩進める、の順を守る
N=1や自己ループで無限ループする	初期化時にtortoise==hareになるケースの考慮漏れ	境界(μ=0,λ=1になるケース)を単体テストで確認する
O(N)の訪問済み配列をこっそり使う	検算コードの消し忘れ	提出コードから訪問済み配列を完全に除去する

次のステップ

発展: 頂点ごとのμ,λの分布から全頂点のサイクルまでの距離をBinary Liftingと組み合わせ、O(1)空間版とO(N)前計算版のトレードオフを比較する。
次回予告: 最小会議室数問題（Minimum Meeting Rooms・貪欲+最小ヒープ）

自己評価

完全理解おおむね理解要復習

Day 155-Q3 — Floyd's Cycle Detection + Brent's Algorithm（サイクル検出）

問題