スタックDFSでオイラーツアー
茶diffが解けない。
まずDFSとは
木を探索する順番は大きく分けてDFSとBFSの２種類があります。
分岐があったらとりあえず片方選んでとにかく先へ先へ一直線に進み、行き止まりになったら分岐まで引き返して次に行くのがDFS。
分岐があったら右を一歩見て左を一歩見て、右を二歩みて左を二歩……と行ったり来たりしながら均等に探索するのがBFS。
アルゴリズム上はDFSはスタックでBFSはキューですね。
昨日出た問題
ABC 213 D Takahashi Tour。(露骨な検索用ワード)
この問題、見ての通り初探索した頂点だけでなく通った頂点は全て記録するタイプのDFSです。
検索ワードはオイラーツアー。
最小共通祖先問題とかで使うそうです。
……が。
ちょっと「オイラーツアー DFS」とかでググってみて下さい。
スタック使ってる人いなくね？
オイラーツアーと相性がいいのは再帰DFS
実はDFSにはスタックDFSだけではなく再帰DFSというのがあり、オイラーツアーではこちらを使うのが基本です。 というわけで、スタックDFSしか知らなかった人は、これを機会に再帰DFSについても勉強してくださいね。
「やだよ、BFSと互換性のない書き方なんて1から覚えるの」
そう考えた偏屈者の私は、謎の執念でスタックオイラーツアーを編み出しました。
絶対再帰DFS勉強した方が早かった。
そもそもオイラーツアーとは
「通ったノードを全て記録する」という言葉に惑わされてはいけません。
通るったって同じ辺を二往復も3往復もするわけではありません。行って帰ったら終わりで、また行く事なんてないわけです。
「帰りも記録するDFS」みたいな言葉はここから来ているわけですね。
そもそもDFSとスタックとは
DFSにおけるスタックとは「次の目的地」です。
これの一番上のグラフを借りてDFSすると、
スタック[1]
頂点1に移動してスタックに[6,2]をプッシュ
スタック[6,2]
頂点2に移動してスタックに[5,3]をプッシュ
スタック[6,5,3]
頂点3に移動してスタックに[4]をプッシュ
スタック[6,5,4]
頂点4に移動
スタック[6,5]
頂点5に移動
スタック[6]
頂点6に移動
スタック[]
終了
となり、探索順だけを記録すると帰りの頂点が記録されないわけです。
……これさ、帰る事を目的としてないから駄目なんじゃん。
帰りも目的地としてプッシュしようよ。
解決策
スタック[1]
頂点1に移動してスタックに[1,6,1,2]をプッシュ
スタック[1,6,1,2]
頂点2に移動してスタックに[2,5,2,3]をプッシュ
スタック[1,6,1,5,2,5,2,3]
頂点3に移動してスタックに[3,4]をプッシュ
スタック[1,6,1,5,2,5,2,3,4]
頂点4に移動
スタック[1,6,1,5,2,5,2,3]
頂点3に移動(辺についてはスタックにプッシュ済みなのでスタックは操作しない)
スタック[1,6,1,5,2,5,2]
頂点2に移動(辺についてはスタックにプッシュ済みなのでスタックは操作しない)
……続く
とこうすればいいわけです。
「プッシュ済みなのでスタックは操作しない」ってどう判別するの？
帰り道でまたスタックに隣接頂点をプッシュしてしまったら大惨事です。スタックが無限に伸びて永久に終わりません。
一般的なスタックDFSではvisited配列を作ってboolで管理していたりします。
ですが今回はワイルドに「一度スタックにプッシュした辺は削除」でいきます。
辺がなければ隣接頂点もなく、スタックを操作したくてもできません。
ACコード
23行目までで隣接リストを作り、24行目でソートしています。
32行目にchildrenという変数が出てきますが、これはただの隣接頂点であり、子だけでなく親も混じってしまっています。
33行目で親をdeleteする事で正真正銘子だけになります。
childrenを作るときに特にdupしたりはしていないので、この時点で現在の頂点から親頂点への辺が切れるわけですね。
34行目以降のループでchildrenを末尾から順に削りつつ、スタックに現在の頂点(36行目)と子頂点(37行目)をプッシュして行きます。
親子関係の記録(35行目)は忘れずに。
茶diffが3連続(出なかった回を飛ばすと4連続)で解けなかったのは人として何かマズい気がする。
Discussion