ダブリングとは
「各頂点の出次数が1以下の有向グラフ($\approx$Functional Graph)」の線形探索を$O(\log K)$で叶える最高のアルゴリズムです！
基本的な考え方は繰り返し二乗法と同じかも。
なんで一思いに「木」って言わないの？
自己ループを含むグラフにも特攻だからです！閉路もあるし、連結してなくてもいいし、なんでもあり？！適切な語彙が見つからんかったんよん(´;ω;｀)
なんで最高なの？
エッホエッホ移動してたのを、過程をぶっ飛ばせるようになるのって、近未来的じゃないですか？？
私は、とても中二心がくすぐられました。
...それをさし置いても、実用性による最高さも、確かなものです！
具体的な実装方法
- 各ノードからの1手後の到着先を保管します
- $1\leq i$以降は、自分より一つ手前の遷移情報をみて、足し合わせます。
- 終わりです
...これだけ？？？
はい、これだけです。とても単純で、しかも強力なので驚かされます。
合計探索回数を$K$としたときに、$O(N\log K)$で組めちゃいます。
実装例
int N; ll K; cin>>N>>K;
int logk=0; while((1LL<<logk)<K) ++logk;
//ステップ1: 一手後の到着先を代入 (iは2^i回数の移動先を示しているのだ)
vector db(logk+1, vector<int>(N)); for(auto& e:db[0]) {
cin>>e; --e;
}
//ステップ2: 手前の遷移を合成して新しいのを作る！
for(int i=1; i<=logk; ++i) for(int j=0; j<N; ++j) db[i][j]=db[i-1][db[i-1][j]];
//最後に いい感じに使ってみる
for(int j=0; j<N; ++j) {
int des=j;
for(int i=0; (1LL<<i)<=K; ++i) if((1LL<<i)&K) des = db[i][des];
cout << des+1 << endl;
}
感想
グラフ探索においては、自己ループを含められるのが最強に面白いと思いました。
高速化の観点においては、埋め合わせが成立するからこそ各計算時間を半減できる考え方は、半分全探索に通じるところがありますね。
今回の実装における状態の疎度の調整は、$2$の乗数でない値も対数時間で求められるようにするためです。故に、線形な動的計画法への応用も考えられます。
こんな常識をぶち壊してくれる問題にあふれている現実に感謝。