Eulerian Trail (Directed) (verify/graph/euler_directed.test.cpp)

View this file on GitHub
Last update: 2024-08-06 17:01:27+02:00
Problem: https://judge.yosupo.jp/problem/eulerian_trail_directed

Depends on

Code

// @brief Eulerian Trail (Directed)
#define PROBLEM "https://judge.yosupo.jp/problem/eulerian_trail_directed"
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("tune=native")
#include "cp-algo/graph/euler.hpp"
#include <bits/stdc++.h>

using namespace std;
using namespace cp_algo::graph;

void solve() {
    int n, m;
    cin >> n >> m;
    graph<directed> g(n);
    g.read_edges(m);
    auto [v0, es] = euler_trail(g);
    if(ssize(es) != m) {
        cout << "No" << "\n";
    } else {
        cout << "Yes" << "\n";
        cout << v0 << ' ';
        for(auto e: es) {cout << g.edge(e).to << ' ';}
        cout << "\n";
        for(auto e: es) {cout << e / 2 << ' ';}
        cout << "\n";
    }
}

signed main() {
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

#line 1 "verify/graph/euler_directed.test.cpp"
// @brief Eulerian Trail (Directed)
#define PROBLEM "https://judge.yosupo.jp/problem/eulerian_trail_directed"
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("tune=native")
#line 1 "cp-algo/graph/euler.hpp"


#line 1 "cp-algo/graph/base.hpp"


#line 1 "cp-algo/graph/edge_types.hpp"


#include <iostream>
#include <cstdint>
namespace cp_algo::graph {
    using node_index = int;
    struct edge_base {
        node_index to;

        edge_base() {}
        edge_base(node_index v): to(v) {}

        static auto read(node_index v0 = 0) {
            node_index u, v;
            std::cin >> u >> v;
            return std::pair{u - v0, edge_base(v - v0)};
        }

        edge_base backedge(int from) const {
            return {from};
        }
    };

    struct weighted_edge: edge_base {
        int64_t w;

        weighted_edge() {}
        weighted_edge(node_index v, int64_t w): edge_base(v), w(w) {}

        static auto read(node_index v0 = 0) {
            node_index u, v;
            int64_t w;
            std::cin >> u >> v >> w;
            return std::pair{u - v0, weighted_edge{v - v0, w}};
        }

        weighted_edge backedge(node_index from) const {
            return {from, w};
        }
    };

    template<typename edge>
    concept edge_type = std::is_base_of_v<edge_base, edge>;
    template<typename edge>
    concept weighted_edge_type = std::is_base_of_v<weighted_edge, edge>;
}

#line 1 "cp-algo/data_structures/stack_union.hpp"


#include <cstddef>
#include <vector>
namespace cp_algo::data_structures {
    template<class datatype>
    struct stack_union {
        stack_union(int n = 0): head(n), next(1), data(1) {}

        void push(int v, datatype const& vdata) {
            next.push_back(head[v]);
            head[v] = std::size(next) - 1;
            data.push_back(vdata);
        }
        template<typename... Args>
        void emplace(int v, Args&&... vdata) {
            next.push_back(head[v]);
            head[v] = size(next) - 1;
            data.emplace_back(std::forward<Args...>(vdata...));
        }

        void reserve(int m) {
            data.reserve(m);
            next.reserve(m);
        }

        size_t size() const {return std::size(head);}
        size_t nodes() const {return std::size(data);}

        std::vector<int> head, next;
        std::vector<datatype> data;
    };
}

#line 5 "cp-algo/graph/base.hpp"
#include <ranges>
#line 7 "cp-algo/graph/base.hpp"
namespace cp_algo::graph {
    using edge_index = int;
    enum type {directed = 0, undirected = 1};
    template<type _undirected, edge_type edge_t = edge_base>
    struct graph {
        static constexpr bool undirected = _undirected;
        graph(int n, int v0 = 0): v0(v0), adj(n) {}

        void add_edge(node_index u, edge_t e) {
            adj.push(u, size(edges));
            edges.push_back(e);
            if constexpr (undirected) {
                adj.push(e.to, size(edges));
            }
            edges.push_back(e.backedge(u));
        }
        void read_edges(node_index m) {
            adj.reserve(m);
            for(edge_index i = 0; i < m; i++) {
                auto [u, e] = edge_t::read(v0);
                add_edge(u, e);
            }
        }
        void call_adjacent(node_index v, auto &&callback, auto &&terminate) const {
            for(int sv = adj.head[v]; sv && !terminate(); sv = adj.next[sv]) {
                callback(adj.data[sv]);
            }
        }
        void call_adjacent(node_index v, auto &&callback) const {
            call_adjacent(v, callback, [](){return false;});
        }
        void call_edges(auto &&callback) const {
            for(edge_index e: edges_view()) {
                callback(e);
            }
        }
        auto nodes_view() const {
            return std::views::iota(0, n());
        }
        auto edges_view() const {
            return std::views::filter(
                std::views::iota(0, 2 * m()),
                [](edge_index e) {return !(e % 2);}
            );
        }
        auto const& incidence_lists() const {return adj;}
        edge_t const& edge(edge_index e) const {return edges[e];}
        node_index n() const {return adj.size();}
        edge_index m() const {return size(edges) / 2;}
    private:
        node_index v0;
        std::vector<edge_t> edges;
        data_structures::stack_union<edge_index> adj;
    };
}

#line 4 "cp-algo/graph/euler.hpp"
#include <algorithm>
#include <utility>
#line 7 "cp-algo/graph/euler.hpp"
namespace cp_algo::graph {
    template<typename graph>
    int euler_start(graph const& g) {
        std::vector<int> deg(g.n());
        constexpr bool undirected = graph::undirected;
        int res = 0;
        g.call_edges([&](edge_index e) {
            int u = g.edge(e ^ 1).to;
            int v = g.edge(e).to;
            res = u;
            deg[u]++;
            deg[v]--;
        });
        if constexpr (undirected) {
            for(auto &it: deg) {
                it = bool(it % 2);
            }
        }
        auto nodes = g.nodes_view();
        auto is_start = [&](int v) {return deg[v] > 0;};
        auto starts = std::ranges::count_if(nodes, is_start);
        if(starts > 1 + undirected) {
            res = -1;
        } else if(starts == 1 + undirected) {
            auto start = *std::ranges::find_if(nodes, is_start);
            res = deg[start] == 1 ? start : -1;
        }
        return res;
    }
    auto euler_trail(auto const& g) {
        int v0 = euler_start(g);
        std::vector<int> trail;
        if(~v0) {
            std::vector<bool> used(g.m());
            auto& adj = g.incidence_lists();
            auto head = adj.head;
            auto dfs = [&](auto &&self, int v) -> void {
                while(head[v]) {
                    int e = adj.data[std::exchange(head[v], adj.next[head[v]])];
                    if(!used[e / 2]) {
                        used[e / 2] = 1;
                        self(self, g.edge(e).to);
                        trail.push_back(e);
                    }
                }
            };
            dfs(dfs, v0);
            std::ranges::reverse(trail);
        }
        return std::pair{v0, trail};
    }
}

#line 6 "verify/graph/euler_directed.test.cpp"
#include <bits/stdc++.h>

using namespace std;
using namespace cp_algo::graph;

void solve() {
    int n, m;
    cin >> n >> m;
    graph<directed> g(n);
    g.read_edges(m);
    auto [v0, es] = euler_trail(g);
    if(ssize(es) != m) {
        cout << "No" << "\n";
    } else {
        cout << "Yes" << "\n";
        cout << v0 << ' ';
        for(auto e: es) {cout << g.edge(e).to << ' ';}
        cout << "\n";
        for(auto e: es) {cout << e / 2 << ' ';}
        cout << "\n";
    }
}

signed main() {
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	euler_tour_00	AC	55 ms	12 MB
g++	euler_tour_01	AC	59 ms	12 MB
g++	euler_tour_02	AC	56 ms	10 MB
g++	euler_tour_03	AC	53 ms	10 MB
g++	example_00	AC	5 ms	4 MB
g++	example_01	AC	5 ms	3 MB
g++	many_same_vertex_00	AC	57 ms	17 MB
g++	many_same_vertex_01	AC	61 ms	17 MB
g++	many_same_vertex_02	AC	58 ms	17 MB
g++	max_random_00	AC	22 ms	8 MB
g++	max_random_01	AC	22 ms	8 MB
g++	max_random_02	AC	28 ms	8 MB
g++	max_random_walk_00	AC	45 ms	15 MB
g++	max_random_walk_01	AC	50 ms	15 MB
g++	max_random_walk_02	AC	66 ms	17 MB
g++	mid_random_00	AC	21 ms	4 MB
g++	mid_random_01	AC	20 ms	4 MB
g++	mid_random_02	AC	20 ms	4 MB
g++	mid_random_walk_00	AC	38 ms	4 MB
g++	mid_random_walk_01	AC	38 ms	4 MB
g++	mid_random_walk_02	AC	39 ms	4 MB
g++	small_random_00	AC	23 ms	4 MB
g++	small_random_01	AC	23 ms	4 MB
g++	small_random_02	AC	22 ms	4 MB
g++	small_random_walk_00	AC	40 ms	4 MB
g++	small_random_walk_01	AC	41 ms	4 MB
g++	small_random_walk_02	AC	41 ms	4 MB