Eulerian Walk
(graph/eulerian_walk.hpp)

• View this file on GitHub
• Last update: 2023-05-27 03:55:18+09:00
• Include: #include "graph/eulerian_walk.hpp"

Description

Euler 路 (グラフのすべての辺を通る路) を一つ見つける．

奇数次の頂点が0個なら Euler 閉路が存在する．奇数次の頂点が2個なら閉路でない Euler 路が存在する．それ以外のときは Euler 路は存在しない．

この実装では Hierholzer のアルゴリズムを用いている．

Operations

• vector<int> eulerian_walk(vector<pair<int, int>> edges, int V)
  • 頂点数 $V$ のグラフ $G$ の辺集合が与えられたとき，$G$ の Euler 路に現れる頂点を順番に返す．存在しない場合は空リストを返す．
  • 時間計算量: $O(E)$

Code

#pragma once
#include <stack>
#include <utility>
#include <vector>

std::vector<int> eulerian_walk(const std::vector<std::pair<int, int>>& edges,
                               int V) {
    std::vector<std::vector<std::pair<int, int>>> G(V);
    std::vector<int> deg(V);
    for (int i = 0; i < (int)edges.size(); ++i) {
        auto [a, b] = edges[i];
        G[a].push_back({b, i});
        G[b].push_back({a, i});
        ++deg[a];
        ++deg[b];
    }
    int s = 0;
    int cnt = 0;
    for (int i = 0; i < V; ++i) {
        if (deg[i] % 2) {
            ++cnt;
            s = i;
        }
    }
    if (cnt != 0 && cnt != 2) return {};
    std::vector<int> ret;
    std::stack<int> st;
    st.push(s);
    std::vector<bool> used(edges.size());
    while (!st.empty()) {
        int u = st.top();
        while (!G[u].empty() && used[G[u].back().second]) G[u].pop_back();
        if (G[u].empty()) {
            ret.push_back(u);
            st.pop();
        } else {
            auto [v, i] = G[u].back();
            G[u].pop_back();
            used[i] = true;
            st.emplace(v);
        }
    }
    return ret;
}

#line 2 "graph/eulerian_walk.hpp"
#include <stack>
#include <utility>
#include <vector>

std::vector<int> eulerian_walk(const std::vector<std::pair<int, int>>& edges,
                               int V) {
    std::vector<std::vector<std::pair<int, int>>> G(V);
    std::vector<int> deg(V);
    for (int i = 0; i < (int)edges.size(); ++i) {
        auto [a, b] = edges[i];
        G[a].push_back({b, i});
        G[b].push_back({a, i});
        ++deg[a];
        ++deg[b];
    }
    int s = 0;
    int cnt = 0;
    for (int i = 0; i < V; ++i) {
        if (deg[i] % 2) {
            ++cnt;
            s = i;
        }
    }
    if (cnt != 0 && cnt != 2) return {};
    std::vector<int> ret;
    std::stack<int> st;
    st.push(s);
    std::vector<bool> used(edges.size());
    while (!st.empty()) {
        int u = st.top();
        while (!G[u].empty() && used[G[u].back().second]) G[u].pop_back();
        if (G[u].empty()) {
            ret.push_back(u);
            st.pop();
        } else {
            auto [v, i] = G[u].back();
            G[u].pop_back();
            used[i] = true;
            st.emplace(v);
        }
    }
    return ret;
}

Back to top page