cpp_src/graph/helper/GetPath.hpp

• View this file on GitHub
• Last update: 2022-01-15 23:16:20+09:00
• Include: #include "cpp_src/graph/helper/GetPath.hpp"

Code

// ABC233F
// pick a path from a to b : O(n)
template <class T>
V<pair<int, Edge<T>>> get_path(const Graph<T>& g, int a, int b) {
    using E = Edge<T>;

    int n = g.size();
    V<int> par(n, -1);
    V<E> par_edge(n);
    auto rec = [&](auto&& f, int v, int p, E pe) -> void {
        par[v] = p;
        par_edge[v] = pe;
        for (auto e : g[v]) {
            if (e.to == p) continue;
            f(f, e.to, v, e);
        }
    };
    rec(rec, a, -1, E());
    if (par[b] == -1) return {};
    V<pair<int, E>> vec;
    int cur = b;
    while (cur != a) {
        vec.emplace_back(par[cur], par_edge[cur]);
        cur = par[cur];
    }
    reverse(ALL(vec));
    return vec;
}

#line 1 "cpp_src/graph/helper/GetPath.hpp"
// ABC233F
// pick a path from a to b : O(n)
template <class T>
V<pair<int, Edge<T>>> get_path(const Graph<T>& g, int a, int b) {
    using E = Edge<T>;

    int n = g.size();
    V<int> par(n, -1);
    V<E> par_edge(n);
    auto rec = [&](auto&& f, int v, int p, E pe) -> void {
        par[v] = p;
        par_edge[v] = pe;
        for (auto e : g[v]) {
            if (e.to == p) continue;
            f(f, e.to, v, e);
        }
    };
    rec(rec, a, -1, E());
    if (par[b] == -1) return {};
    V<pair<int, E>> vec;
    int cur = b;
    while (cur != a) {
        vec.emplace_back(par[cur], par_edge[cur]);
        cur = par[cur];
    }
    reverse(ALL(vec));
    return vec;
}

Back to top page