Spaghetti Source logo

無向オイラー路

説明

無向グラフにおいて,すべての辺を一度ずつ使用する経路を無向オイラー路という.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

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

Last Modified: 2007.11.13 09:29:36.