cpp_src/graph/EulerPath.hpp

• View this file on GitHub
• Last update: 2022-05-22 15:10:18+09:00
• Include: #include "cpp_src/graph/EulerPath.hpp"
• Link: https://codeforces.com/contest/508/submission/92099335

Code

// old !!!!
// Hierholzer algorithm
// https://codeforces.com/contest/508/submission/92099335

// directed
// destruct graph
// todo : add BEST theorem

template <class E>
V<int> EulerianPath(const int s, VV<E>& g) {
    auto dfs = [&](auto&& self, int u, V<int>& path) -> void {
        while (!g[u].empty()) {
            int v = g[u].back();  // E : int
            g[u].pop_back();
            self(self, v, path);
        }
        path.push_back(u);
    };
    V<int> path;
    dfs(dfs, s, path);
    reverse(path.begin(), path.end());
    return path;
}

#line 1 "cpp_src/graph/EulerPath.hpp"
// old !!!!
// Hierholzer algorithm
// https://codeforces.com/contest/508/submission/92099335

// directed
// destruct graph
// todo : add BEST theorem

template <class E>
V<int> EulerianPath(const int s, VV<E>& g) {
    auto dfs = [&](auto&& self, int u, V<int>& path) -> void {
        while (!g[u].empty()) {
            int v = g[u].back();  // E : int
            g[u].pop_back();
            self(self, v, path);
        }
        path.push_back(u);
    };
    V<int> path;
    dfs(dfs, s, path);
    reverse(path.begin(), path.end());
    return path;
}

Back to top page