ダブリングではなくループ検出
ダブリングでなはくループ検出
ループ検出で解くのが素直な問題を「これはダブリングだな」と勘違いすることが2回あったのでページにした
頂点数VのグラフでN個先を読む時
ダブリング
O(VlogN)の前処理で、本処理をO(logN)にできる
本処理をV回以上繰り返すなら得
logNが大きすぎるとこれでも無理
ループ検出
単一始点なら最悪O(V)で前処理できる
任意始点の時にどうすれば良いか？素朴にやればO(V^2)
Nがループに入るくらい大きい場合には、ループに入るまでの距離を引いて、ループ長で剰余を取る
O(1)
比較
任意始点でNが高々Vならダブリングの方が前処理が軽い
単一始点ならループ検出の方が有利
任意始点でもNがやたら大きいならループ検出