グラフライブラリまとめ
- DFS
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); } }; } }
実装例
https://atcoder.jp/contests/abc222/submissions/31901254
- 数列DFS
auto dfs_ns = [&](auto self, ll len, pll range, vl now, vvl& res) -> void
- len: 生成する数列の長さ
- range: 使用できる数字の半開区間指定[first,second)
- now: 現在の数列状態
- res: 生成した数列を返す
#include <bits/stdc++.h> namespace NyaaLIB_GTL { namespace DFS_NS { // Numerical Sequence using ll = long long; using pll = std::pair<ll, ll>; using vl = std::vector<ll>; using vvl = std::vector<std::vector<ll>>; auto dfs_ns = [&](auto self, ll len, pll range, vl now, vvl& res) -> void { if ((ll)a.now.size() == len) { // 末端に到達したときの処理 res.push_back(now); return; } for (ll i = range.first; i < range.second; i++) { now.push_back(i); self(self, now); now.pop_back(); } }; } }
- 木構造メモ化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]; }; }