深さ優先探索のテンプレート
auto dfs=[&](auto self, State& s, Undo u, auto& res)->void
- s: 状態
- u: 復元
- res: 結果
struct Undo { nyaa; }; struct State { nyaa; }; auto dfs=[&](auto self, State& s, Undo u, auto& res)->void { if(末端ノードの条件) { res に結果を追加; return; } for(枝の数だけ繰り返す) { 次状態に更新する前に復元に必要な情報を u に保存; 状態 s を次状態へ更新; self(self,s,u,res); 状態 s を u を使って復元; } };
陽に木のデータ構造を持つ深さ優先探索
auto dfs = [&](auto self, wgraph& g, ll now, ll root) -> void
- g: 重み付き隣接リスト
- now: 今みている頂点
- root: 頂点nowに対する根(DFS1回目の呼び出しでは-1を指定するのが典型)
#include <bits/stdc++.h> namespace NyaaLIB_GTL { namespace DFS { using ll = long long; using wgraph = std::vector<std::vector<std::pair<ll, ll>>>; auto dfs = [&](auto self, wgraph& g, ll now, ll root) -> void { for (auto& [next, cost] : g[now]) { if (next == root) continue; self(self, g, next, now); } }; } }
木構造メモ化DFS
計算済を二度計算すると不味いので(for文の前に) if(update[now]) return; が必要
計算が完了したとき(for文の後に) update[now] = true; が必要
for文の中では計算済みかどうかで以下のように場合分けをする
1. 計算済の値が使える→O(1)で処理可能
2. 計算済でない値を使う→先に再帰的に計算させる必要があるので、何らかの処理は再帰関数の後に書く
#include <bits/stdc++.h> namespace NyaaLIB { /** * @brief 木構造メモ化DFS * @param _g グラフ * @param _update 計算済みチェック * @param _dp メモ化した値 * @param _now 今みている頂点 * @param _root 頂点nowに対する根 * @note メモ化DPの応用例 **/ auto GTL_NyaaTreeMemoDFS = [&](auto self, auto& _g, auto& _update, auto& _dp, auto _now, auto _root) -> void { using ll = long long; using vb = std::vector<bool>; using vll = std::vector<ll>; using wlg = std::vector<std::vector<std::pair<ll, ll>>>; wlg& g = _g; vb& update = _update; vll& dp = _dp; ll now = _now; ll root = _root; if (update[now]) return; for (auto [af, cost] : g[now]) { if (af == root) continue; if (update[af]) { // すでに計算済み // nyaa; } else { // 計算済みではないので再帰的に計算してから結果を利用する self(self, g, update, dp, af, now); // nyaa; } } update[now] = true; }; }
実装例
https://atcoder.jp/contests/abc037/submissions/27743394
2Dグリッドに対するDFS
#include <bits/stdc++.h> namespace NyaaLIB { /** * @brief 2Dグリッドに対するDFS * @param ysz y-size * @param xsz x-size * @param now 現局面 * @note 状態DFSの応用例 **/ auto GTL_NyaaDFS2D = [&](auto self, long long ysz, long long xsz, std::vector<std::vector<long long>>& now) -> long long { // 末端処理 if (true) return 999999999; std::vector<std::vector<long long>> test(ysz, std::vector<long long>(xsz, 0)); for (ll y = 0; y < ysz; y++) for (ll x = 0; x < xsz; x++) { // 現局面からの遷移 now[y][x] = 1; test[y][x] = self(self, now); now[y][x] = 0; } // 現局面からの遷移を全て処理した結果などを追記 return test[0][0]; }; }