7K12 blog

猫でも分かるアルゴリズム解説

NyaaLIB_GTL

グラフライブラリまとめ

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

  • 数列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();
			}
		};
	}
}

計算済を二度計算すると不味いので(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];
	};
}

実装例
https://atcoder.jp/contests/abc025/submissions/27466506