src/Graph/TreeOrders.hpp

• View this file on GitHub
• Last update: 2020-07-12 16:30:58+09:00
• Include: #include "src/Graph/TreeOrders.hpp"

概要

木を受け取り、dfs順を返す。 pre_order: トップダウン。dfsで訪れた順。 post_order: ボトムアップ。木dpとかで使う。

Code

/// @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;
}

Back to top page