無向オイラー路

説明

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

• すべての頂点の次数が偶数
• s と t の次数が奇数で，残りが偶数．

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

計算量

O(E)

使い方

const Graph &g

有向グラフ．

int s

始点．

vector<int> &path

オイラー路．

ソースコード

void visit(const Graph &g, vector< vector<int> > &adj, int s, vector<int> &path) {
  FOR(e, g[s]) if (adj[e->src][e->dst]) {
    --adj[e->src][e->dst];
    --adj[e->dst][e->src];
    visit(g, adj, e->dst, path);
  }
  path.push_back(s);
}
bool eulerPath(const Graph &g, int s, vector<int> &path) {
  int n = g.size();
  int odd = 0, m = 0;
  REP(i, n) {
    if (g[i].size() % 2 == 1) ++odd;
    m += g[i].size();
  }
  m /= 2;
  if (odd == 0 || (odd == 2 && g[s].size() % 2 == 0)) {
    vector< vector<int> > adj(n, vector<int>(n));
    REP(u, n) FOR(e, g[u]) ++adj[e->src][e->dst];
    path.clear();
    visit(g, adj, s, path);
    reverse(ALL(path));
    return path.size() == m + 1;
  }
  return false;
}

Verified

• UVA 10053 - The Necklace