Spaghetti Source logo

有向オイラー路

説明

有向グラフにおいて,すべての辺を一度ずつ使用する経路を有向オイラー路という.s を始点とし,t を終点とするオイラー路が存在するためには

のどちらかであることが必要十分である.一つ目の条件を満たすとき,オイラー路は特にオイラー閉路になる.

計算量

O(E)

使い方

const Graph &g
有向グラフ.
int s
始点.
vector<int> &path
オイラー路.

ソースコード

void visit(Graph& g, int a, vector<int>& path) {
  while (!g[a].empty()){
    int b = g[a].back().dst;
    g[a].pop_back();
    visit(g, b, path);
  }
  path.push_back(a);
}
bool eulerPath(Graph g, int s, vector<int> &path) {
  int n = g.size(), m = 0;
  vector<int> deg(n);
  REP(u, n){
    m += g[u].size();
    FOR(e, g[u]) --deg[e->dst]; //  in-deg
    deg[u] += g[u].size();      // out-deg
  }
  int k = n - count(ALL(deg), 0);
  if (k == 0 || (k == 2 && deg[s] == 1)) {
    path.clear();
    visit(g, s, path);
    reverse(ALL(path));
    return path.size() == m + 1;
  }
  return false;
}

Verified

前原 貴憲(maehara@prefield.com).

Last Modified: 2007.11.13 09:03:42.