This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub knshnb/competitive_library
#include "src/Graph/TreeOrders.hpp"
木を受け取り、dfs順を返す。 pre_order: トップダウン。dfsで訪れた順。 post_order: ボトムアップ。木dpとかで使う。
/// @docs src/Graph/TreeOrders.md std::vector<int> pre_order(const std::vector<std::vector<int>>& g, int s = 0) { std::vector<int> ord; ord.reserve(g.size()); auto dfs = [&g, &ord](auto&& self, int v, int prv) -> void { ord.push_back(v); for (int s : g[v]) { if (s == prv) continue; self(self, s, v); } }; dfs(dfs, s, -1); return ord; } std::vector<int> post_order(const std::vector<std::vector<int>>& g, int s = 0) { std::vector<int> ord; ord.reserve(g.size()); auto dfs = [&g, &ord](auto&& self, int v, int prv) -> void { for (int s : g[v]) { if (s == prv) continue; self(self, s, v); } ord.push_back(v); }; dfs(dfs, s, -1); return ord; }
#line 1 "src/Graph/TreeOrders.hpp" /// @docs src/Graph/TreeOrders.md std::vector<int> pre_order(const std::vector<std::vector<int>>& g, int s = 0) { std::vector<int> ord; ord.reserve(g.size()); auto dfs = [&g, &ord](auto&& self, int v, int prv) -> void { ord.push_back(v); for (int s : g[v]) { if (s == prv) continue; self(self, s, v); } }; dfs(dfs, s, -1); return ord; } std::vector<int> post_order(const std::vector<std::vector<int>>& g, int s = 0) { std::vector<int> ord; ord.reserve(g.size()); auto dfs = [&g, &ord](auto&& self, int v, int prv) -> void { for (int s : g[v]) { if (s == prv) continue; self(self, s, v); } ord.push_back(v); }; dfs(dfs, s, -1); return ord; }