オイラー路の構築

C++ 用ライブラリ一覧に戻る

ソースコード

nachia/graph/eulerian-trail.hpp

主な機能

グラフの辺をすべてちょうど $1$ 回ずつ通る walk があれば、構築する。

関数 EulerianTrail

テンプレート引数

auto EulerianTrail(const Graph& graph);

• 頂点数 : $1\leq n\leq 10^8$
• 辺数 : $0\leq m\leq 10^8$
• グラフの設定が有向か無向かによって動作が適切に変化する。

返り値の型は次の通り。

struct Result {
    int length;
    int start;
    std::vector<int> edges;
};

返り値として、

• $m=0$ ならば、 $(0,0,())$ として返す。
• オイラー路が存在しなければ length == -1 として返す。
• オイラー路が存在すれば、
  • 辺の個数を length 、
  • 始点を start 、
  • 通る辺を順番に edges に格納して返す。

---

TOP PAGE