深さ優先探索 auto dfs

深さ優先探索のテンプレート

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 を使って復元;
	}
};

本質

状態 s を次の深さのノードの状態に更新したあと再帰関数で遷移する。再帰関数から戻ってきたとき状態 s が次の深さのノードの状態のままになっているため、必ず状態の更新内容を復元する操作が必要。このとき s は参照渡しで良いが u は値渡しでないと前状態として保存できないので注意。

実装例

https://atcoder.jp/contests/abc161/submissions/39949683

陽に木のデータ構造を持つ深さ優先探索

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/33133852

木構造メモ化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];
	};
}