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