競プロにおけるオイラー路とその応用について
この記事はCompetitive Programming Advent Calendar 2017の12月8日の記事です。
競プロにおけるオイラー路とその応用について
はじめに
この記事では、オイラー路の基礎、そして主に競技プログラミングで使えるその応用についてできるだけ詳しく書きます。
最初の方は基礎的な定義や解説を書いているので、オイラー路とは何かをすでにご存知の方は、無向オイラー路の構築あたりからどうぞ。
説明で出てくるグラフは特に断らない限り連結で、多重辺や自己辺は基本的にあってもよいものとします。
また、もし必要があればこの記事に載せたコードはすべて自由に使って頂いて構いません。
例題で扱った問題は、はまやんはまやんさんによる記事からいくつか適切に選びました。情報ありがとうございます。
なにか問題等ありましたらTwitter @Ymgch_Kまで連絡いただけるとありがたく思います。
無向グラフのオイラー路
まずは無向グラフにおけるオイラー路（無向オイラー路）を考えます。以下の無向グラフにおいてオイラー路の一例を示すことができるでしょうか？
このグラフの場合、頂点7からスタートして、例えば以下のような順ですべての辺をちょうど一回使って、オイラー路を構成することができます。
このような、オイラー路が存在するグラフを準オイラーグラフと呼びます。あるグラフが準オイラーグラフになるための必要条件について考えます。
あるオイラー路をとったとき、その路上の始点と終点を除く頂点に注目すると、必ず入ってくる辺と出て行く辺のペアを作れることがわかります。よって、始点と終点を除くどの頂点についても必ず次数が偶数である必要があります。一方、始点については出て行く辺が入ってくる辺に比べて一つ多く、終点については入ってくる辺が出て行く辺に比べて一つ多いため、いずれも次数が奇数であることがわかります。
よって次のことが言えます。
★あるグラフが準オイラーグラフであるための必要条件は、そのグラフの頂点のうち次数が奇数であるものがちょうど2個であることである。
また、始点と終点が一致する場合は、オイラー閉路が存在することになりますが、そのようなグラフを特にオイラーグラフと呼びます。オイラーグラフについても同様の考察をすることで、以下の必要条件が言えます。
★あるグラフがオイラーグラフであるための必要条件は、そのグラフのすべての頂点の次数が偶数であることである。
有向グラフのオイラー路
次に有向グラフにおけるオイラー路（有向オイラー路）について説明します（ほとんど同じ）。次の有向グラフは有向オイラーグラフです。
なぜなら、例えば次のような、始点、終点をともに頂点4とするオイラー閉路が存在するからです。
無向グラフのときと同様の考察をすると、各頂点についてやはり、入ってくる辺の数と出て行く辺の数が等しくなっていなければならないので、次の2つの必要条件が言えます。
★ある有向グラフが有向準オイラーグラフであるための必要条件は、ある1頂点について入次数 + 1 = 出次数が成り立ち（始点）、また別のある1頂点について入次数 = 出次数 + 1 が成り立ち（終点）、他のすべての頂点について入次数 = 出次数が成り立つことである。
★ある有向グラフが有向オイラーグラフであるための必要条件は、すべての頂点について入次数 = 出次数が成り立つことである。
無向オイラー路の構築
さて、今までの議論では、オイラー路が構築されたときの、そのグラフの必要条件だけを見てきました。以下では逆にそのようなグラフに対して、実際にオイラー路が構築可能であることを示します。
まず次の条件を満たす無向グラフにおいて、オイラー路を一つ構築します。
★次数が奇数である頂点がちょうど2個である。
ここでは、ハイヤーホルザーのアルゴリズム（Hierholzer's Algorithm）によってオイラー路を構築します（Fleury's algorithmというものもありますが、こちらは実装量的にも計算量的にも非効率です）。
まず次数が奇数である頂点をそれぞれ始点 、終点 とおきます。点 から任意の順番に辺を選んで破壊しながら進み、進める辺がなくなるまで進むことを考えます。このとき、行きつく先は必ず になることが言えます。なぜなら、 を出発した瞬間に、 以外のすべての頂点（ も含む）の次数は偶数であると考えることができ、従って 以外の頂点に進んだ場合は必ずその頂点から出ていける辺も存在するため、それ以上進めなくなる点としてありうるのは だけであるからです。
この時点ですべての辺を使っているなら、その路がオイラー路になるため、これで構築が終了します。そうでない場合は、すでに構築した路（これを路 とする）を基準にオイラー路を構築することができます。
具体的には、すべての辺を使うまで、次の操作を繰り返すことでオイラー路を構築できます。
（操作）路 を の方から順に戻っていくと、まだ使っていない辺をもつ頂点に達するはずである。この点を とすると、 から任意の残っている辺を使って、それ以上進めなくなるまで任意の進み方で進む。その結果、必ず点 自身に戻るのでその路を とします。路 において、その途中の点 から路 をそのタイミングで通ったかのように にマージする。すなわち とする。
点 から任意の経路を進むとき、必ず 自身に戻る（路 が閉路になる）ことは、上記と同じように示せます。すなわち、 を出発した瞬間以降、点 以外の全ての点の次数は偶数になっているため、それ以上進めなくなるまで進んだ場合、必ず に戻るはずです。
以上の構築は文章だとわかりにくいので、以下の簡単な例で見てみます（特殊な例を挙げているだけなんじゃないかと思う人がもしいれば、いろんなグラフで自分で実験してみることをオススメします！）。
まず点 から に達するまで任意の進み方をした（ から辺を破壊しながら進み続けると、どうやっても にしかたどり着けないことに気付くはずです）ところ、以下のような順番で辺を通ったとします。
これが路 に対応しています。一方、残る辺は次のようになります。
辺が残っているので、上の操作をします。つまり、路 を の方から順にみていき、まだ使っていない辺に出会うまで戻ります。すると頂点5（これが上の点 に対応します）に達した時に、他の辺が使えることがわかるので、そこから任意の方向に進みます。すると、頂点5から頂点5自身に戻るように以下のように進むことができます。
これが路 に対応しています。よって、順番に気をつけながら、元の路にこれをマージすることで、次のオイラー路を得ることができます。
同様に考えると次の条件を満たす無向グラフにおいて、オイラー閉路を構築することができます。
★すべての頂点の次数が偶数である。
これは任意の頂点を上の に対応させることで、全く同様に構築可能です。
実装
さて、ここから実装について書いていきます。
まず、あるグラフについて、オイラー(閉)路が存在するかどうかというのは、各頂点の次数の偶奇をチェックするだけでよいため、オイラー路が構築可能であると確認しているものと仮定します。
すると無向オイラー路の構築は以下のシンプルなコードによって実現できます。
void dfs(int u, vector<int> &trail) { for (int v = 0; v < g.size(); v ++) if (g[u][v] > 0) { g[u][v] --, g[v][u] --; dfs(v, trail); } trail.push_back(u); }
より正確には、このアルゴリズムでオイラー路の逆順の一例が得られます。ただしgは隣接行列のvectorであるとします。空っぽのtrailとスタートの頂点sを用いてdfs(s, trail)で呼び出して、その結果をreverseすればよいです。理由は上に述べた通りですが、辺を壊しながらひたすら進めるだけ進んで、進めなくなったらその頂点を確定させることで、最後に到達する頂点から順番に決めていくことができます。
これを隣接リストで書くと次のようになります。
void dfs(int u, vector<int> &trail) { while (!g[u].empty()) { int v = g[u].back(); g[u].pop_back(); for (int i = 0; i < g[v].size(); i ++) { if (g[v][i] == u) { g[v].erase(g[v].begin() + i); break; } } dfs(v, trail); } trail.push_back(u); }
有向オイラー路の構築は辺の破壊が容易なので、もっとあっさりと書けます。
//隣接行列 void dfs(int u, vector<int> &trail) { for (int v = 0; v < n; v ++) if (g[u][v] > 0) { g[u][v] --; dfs(v, trail); } trail.push_back(u); } //隣接リスト void dfs(int u, vector<int> &trail) { while (!g[u].empty()) { int v = g[u].back(); g[u].pop_back(); dfs(v, trail); } trail.push_back(u); }
以上の実装をまとめると、以下のようなライブラリとして使うことができます。あとで示す例題5のような、本当にオイラー路を求めるだけというようなときに瞬時に使えます。
//gが隣接リスト //gを破壊する vector<int> EulerianTrail(const int s, vector<vector<int>> &g, const bool directed) { function<void (int, vector<int> &)> dfs = [&](int u, vector<int> &trail) { while (!g[u].empty()) { int v = g[u].back(); g[u].pop_back(); if (!directed) { for (int i = 0; i < g[v].size(); i ++) { if (g[v][i] == u) { g[v].erase(g[v].begin() + i); break; } } } dfs(v, trail); } trail.push_back(u); }; vector<int> trail; dfs(s, trail); reverse(trail.begin(), trail.end()); return trail; } //gが隣接行列 //gを破壊する vector<int> EulerianTrail(const int s, vector<vector<int>> &g, const bool directed) { function<void (int, vector<int> &)> dfs = [&](int u, vector<int> &trail) { for (int v = 0; v < g.size(); v ++) if (g[u][v] > 0) { g[u][v] --; if (!directed) g[v][u] --; dfs(v, trail); } trail.push_back(u); }; vector<int> trail; dfs(s, trail); reverse(trail.begin(), trail.end()); return trail; }
実装から明らかですが、連結なグラフにおけるオイラー路構築の時間計算量は です。オイラー路の解説と実装は以上になります。
ここから先は、5つの例題とその解法を、難易度順（？）に載せています。ここまでに述べたことを理解していればそこまで難しくはないので、ぜひすべて解いてオイラー路のプロになりましょう！
例題1（★）
問題概要：省略です。
与えられるグラフが無向準オイラーグラフかどうかを判定するだけですね。
実装
#include <cstdio> #include <vector> using namespace std; int main() { int a, b; vector<pair<int, int>> es; while (~scanf("%d%d", &a, &b)) es.emplace_back(a, b); int k = 0; while (k < es.size()) { vector<int> deg(105); while (es[k].first != 0) { deg[es[k].first] ++; deg[es[k].second] ++; k ++; } k ++; bool ok = true; for (int i = 3; i <= 105; i ++) if (deg[i] & 1) ok = false; if (deg[1] % 2 == 0 || deg[2] % 2 == 0) ok = false; puts(ok ? "OK" : "NG"); } return 0; }
例題2（★★）
Kobutanukitsuneko | Aizu Online Judge
問題概要：文字列がいくつか与えられるので、そのすべてを使ってしりとりができるるかどうかを判定せよ。ただし、最後の文字列の語尾と最初の文字列の先頭も一致していなければいけない。
しりとりで重要なのは先頭と語尾の文字だけなので、そこに注目します。そこで、「"euler"という文字列を使う」という条件を「頂点"e"から頂点"r"に張られた辺を使う」という風に読み替えることができます。
この方法でグラフを構築すると、ある頂点からスタートして、すべての辺を重複なく使って元の頂点に戻るような路が存在するかを判定する問題に変わりますね。
したがって、このグラフが有向オイラーグラフであるかどうかを判定すればよいです。これをそのまま書くと次のようになります。
#include <iostream> #include <cstdio> #include <algorithm> #include <string> #include <vector> using namespace std; int main() { int n; while (scanf("%d", &n), n) { vector<int> in_deg(26), out_deg(26); for (int i = 0; i < n; i ++) { string s; cin >> s; int a = s[0] - 'a'; int b = s.back() - 'a'; in_deg[a] ++, out_deg[b] ++; } bool ok = true; for (int i = 0; i < 26; i ++) ok &= in_deg[i] == out_deg[i]; puts(ok ? "OK" : "NG"); } return 0; }
しかしこれでは不十分で、連結でないオイラーグラフが2個以上あったりする場合などに対応できていません。つまりグラフの連結性を確認しておかなければいけません（ここでいう連結とは、グラフを無向グラフとみたときに連結であるということです）。よってUnionFindなどを使って連結性もみると、以下のようなコードになります。
実装
#include <iostream> #include <cstdio> #include <algorithm> #include <string> #include <vector> using namespace std; struct UnionFind { int n; vector<int> parent; vector<int> rank; vector<int> num; int find(int x) { if (parent[x] == x) return x; return parent[x] = find(parent[x]); } UnionFind(int n_) { n = n_; parent.resize(n); for (int i = 0; i < n; i ++) parent[i] = i; rank.assign(n, 0); num.assign(n, 1); } void unite(int x, int y) { if ((x = find(x)) != (y = find(y))) { if (rank[x] < rank[y]) { parent[x] = y; num[y] += num[x]; } else { parent[y] = x; if (rank[x] == rank[y]) rank[x] ++; num[x] += num[y]; } n --; } } bool same(int x, int y) { return find(x) == find(y); } int get() { return n; } int get(int x) { return num[find(x)]; } }; int main() { int n; while (scanf("%d", &n), n) { UnionFind uf(26); vector<int> in_deg(26), out_deg(26); for (int i = 0; i < n; i ++) { string s; cin >> s; int a = s[0] - 'a'; int b = s.back() - 'a'; in_deg[a] ++, out_deg[b] ++; uf.unite(a, b); } bool ok = true; int cnt = 0; for (int i = 0; i < 26; i ++) if (in_deg[i] > 0 || out_deg[i] > 0) cnt ++; for (int i = 0; i < 26; i ++) { if (in_deg[i] > 0 || out_deg[i] > 0) { if (uf.get(i) != cnt) { ok = false; break; } } } for (int i = 0; i < 26; i ++) ok &= in_deg[i] == out_deg[i]; puts(ok ? "OK" : "NG"); } return 0; }
例題3 (★★★）
問題概要：長さ3の文字列が 個与えられます。これらがある一つの文字列のTrigramになっているかを判定し、そうであるならばその文字列を出力せよ。
例題2とほとんど同じ発想をします。つまりまず「文字列"abc"を使う」という条件を「頂点"ab"から頂点"bc"に張られた辺を使う」という風に読み換えてしまうことができます。
よってそのグラフが有向(準)オイラーグラフであるかどうかを判定すればよいです。ただし、こちらもやはりグラフが連結でない場合は明らかにダメなことに気をつけます。
例題2と違ってこちらは構築までしなければいけないので、上の構築のアルゴリズムを書きます。UnionFindなどによる連結性の判定は必要なく、オイラー路を構築したあとにまだ使っていないノードがあるかどうかをみればよいです。
実装
#include <iostream> #include <cstdio> #include <algorithm> #include <string> #include <vector> #include <map> #include <functional> using namespace std; //隣接リスト //gを破壊する vector<int> EulerianTrail(const int s, vector<vector<int>> &g, bool directed, vector<bool> &used) { function<void (int, vector<int> &)> dfs = [&](int u, vector<int> &trail) { used[u] = true; while (!g[u].empty()) { int v = g[u].back(); g[u].pop_back(); if (!directed) { for (int i = 0; i < g[v].size(); i ++) { if (g[v][i] == u) { g[v].erase(g[v].begin() + i); break; } } } dfs(v, trail); } trail.push_back(u); }; vector<int> trail; dfs(s, trail); reverse(trail.begin(), trail.end()); return trail; } int main() { int n; scanf("%d", &n); //文字列を頂点に変換 map<string, int> stov; //2文字 -> 頂点 map<int, string> vtos; //頂点 -> 2文字 int k = 0; vector<pair<int, int>> es; for (int i = 0; i < n; i ++) { string s; cin >> s; string a = s.substr(0, 2); string b = s.substr(1, 2); if (!stov.count(a)) stov[a] = k ++; if (!stov.count(b)) stov[b] = k ++; es.emplace_back(stov[a], stov[b]); if (!vtos.count(stov[a])) vtos[stov[a]] = a; if (!vtos.count(stov[b])) vtos[stov[b]] = b; } //グラフを構築する int m = n; n = stov.size(); vector<vector<int>> g(n); vector<int> in_deg(n); //入次数を数える。出次数はg[i].size()でよい for (int i = 0; i < m; i ++) { int a = es[i].first, b = es[i].second; g[a].push_back(b); in_deg[b] ++; } //オイラー路を構築可能かを判定する int s = -1, t = -1; for (int i = 0; i < n; i ++) { if ((int) g[i].size() == in_deg[i] + 1 && !~s) s = i; else if ((int) g[i].size() + 1 == in_deg[i] && !~t) t = i; else if (g[i].size() == in_deg[i]) continue; else return !printf("NO\n"); } if (s == -1) s = 0; //オイラー閉路の場合 //オイラー路を構築する vector<bool> used(n, false); auto trail = EulerianTrail(s, g, true, used); //連結性を判定する for (int i = 0; i < n; i ++) if (!used[i]) return !printf("NO\n"); cout << "YES" << endl; //オイラー路の順番に辿って文字列を出力する for (int i = 0; i < trail.size(); i ++) { cout << vtos[trail[i]][0]; if (i == trail.size() - 1) cout << vtos[trail[i]][1] << endl; } return 0; }
例題4（★★★★）
問題概要：無向グラフが与えられるので、すべての辺に適切に向きをつけて、入次数と出次数が等しい頂点数を最大化せよ。
少しずつオイラー路っぽさが見えにくい問題になってきました。まず、すべての頂点の次数が偶数の場合を考えてみることにします。
するとそのグラフは無向オイラーグラフであることがわかります。ここで任意のオイラー閉路を作って、それを有向グラフのように見てやると、これは有向オイラーグラフであることになります。
よってすべての頂点について入次数と出次数が等しくなるように向きづけることができました。
ところで、もとのグラフには次数が奇数である頂点が存在します。このような頂点は、どのように向きづけても条件を満たすようにはできません。
そこで、次数が奇数であるような頂点のペアに対して勝手に1本辺を加えてやることを考えます。このようなペアは必ず余すことなく作ることができます（すべての辺は、ある2頂点の次数をそれぞれ1増加させているため、次数が奇数であるような頂点は必ず偶数個あるからです）。これですべての頂点の次数が偶数になったので、このグラフの上でオイラー路を構築すると考えればよいです。
これを連結成分ごとにやれば、すべての辺に向きをつけることができます。ただし勝手に付け加えた辺の向きづけは出力しないように注意します。
実装
#include <cstdio> #include <algorithm> #include <vector> #include <cassert> #include <functional> using namespace std; int main() { int t; scanf("%d", &t); while (t --) { int n, m; scanf("%d%d", &n, &m); //グラフ構築 vector<vector<int>> g(n, vector<int> (n, 0)); //nが小さいので隣接行列でやる方がよい for (int i = 0; i < m; i ++) { int a, b; scanf("%d%d", &a, &b); a --, b --; g[a][b] ++; g[b][a] ++; } //次数が奇数である頂点を列挙する。 vector<int> odd; int ans = n; for (int i = 0; i < n; i ++) { int deg = 0; for (int j = 0; j < n; j ++) deg += g[i][j]; if (deg & 1) { odd.push_back(i); ans --; } } assert(odd.size() % 2 == 0); //そのような頂点の個数は必ず偶数個ある //次数が奇数である頂点を適当につないでいく。追加した辺であることがわかるようにしておく。これでつないだ結果多重辺になる場合もある。 vector<vector<int>> added(n, vector<int> (n, 0)); for (int i = 0; i < odd.size(); i += 2) { int a = odd[i], b = odd[i + 1]; g[a][b] ++, g[b][a] ++; added[a][b] ++, added[b][a] ++; } //任意の順番で各連結成分のオイラー路を構築し、-1で連結成分ごとに区切っている vector<int> used(n, false); function<void (int, vector<int> &)> dfs = [&](int u, vector<int> &trail) { used[u] = true; for (int v = 0; v < n; v ++) if (g[u][v] > 0) { g[u][v] --, g[v][u] --; dfs(v, trail); } trail.push_back(u); }; vector<int> trail; for (int i = 0; i < n; i ++) { if (!used[i]) { dfs(i, trail); trail.push_back(-1); } } reverse(trail.begin(), trail.end()); //付け加えた辺以外の向きを出力する printf("%d\n", ans); for (int i = 0; i < trail.size() - 1; i ++) { if (trail[i] == -1 || trail[i + 1] == -1) continue; int a = trail[i], b = trail[i + 1]; if (added[a][b]) { added[a][b] --; added[b][a] --; continue; } printf("%d %d\n", a + 1, b + 1); } } return 0; }
例題5（★★★★★）
最後です。
問題概要：無向グラフが与えられるので、各頂点について入次数と出次数がともに偶数個になるように辺の向きづけを行い、必要に応じて最小限の個数だけ辺を追加せよ。
まず最初に例題4と同様に、次数が奇数個の頂点が存在する場合、辺を追加しない限り条件を満たすようにできません。よって、これらの頂点同士を無向辺でつなぎます。とりえあず最低でも(次数が奇数の頂点数 / 2)本の辺は必ず追加しなければいけないのは明らかです。
この操作によってすべての頂点の次数が偶数になりました。そうなると、今まで通りオイラー閉路を構築したい気持ちになるので、構築してみることにします。
さて、このオイラー路は当然条件を満たしているわけではありません。そこで次のようなことを考えます。
オイラー路というのは、各頂点を通過するたびに、その頂点の入次数と出次数を1ずつ増やすものでした。これを、入次数または出次数のいずれかを2増やす、という風にできないでしょうか。
それをするために、オイラー路の向きを、交互に逆向きにすることを考えます。すると、頂点を通過するたびに入次数または出次数のいずれかが2増えることになります。よって、この方法ですべての辺を使って各頂点を通過すれば、条件を満たすようにできるはずです！
しかし、このオイラー閉路におけるスタートの頂点はまだ条件を満たしていない可能性があります。具体的には、オイラー閉路ではすべての辺を使っているので、すべての辺の個数が奇数の場合はまだ条件を満たしていません。その場合は、スタートの頂点は入次数も出次数も奇数になっているはずなので、そこに自己辺を追加することで条件を満たすようにできます。
この最後の追加が最小値の条件を満たすかどうかというのは次のようにして示せます。
まずグラフの構築の仕方によらず、上にも述べたように最低限必ず(次数が奇数の頂点数 / 2)本の辺は追加しなければいけません。この結果できるグラフの辺の総数は一意に定まります。辺の総数が奇数の場合は条件を満たすようにはできないことを言えばよいです。
グラフのある2頂点（同一の場合も含む）に有向辺を付け加える操作を行うと、片方は入次数が、もう片方は出次数が1増加します。辺の総数が奇数個であるならば、この操作の回数は奇数回なので、入次数の総和と出次数の総和はどちらも必ず奇数になっているはすです。よってこのとき少なくとも1頂点については条件を満たしていないことがわかります。これで最小性が言えました。
以上を実装すると以下のようになります。
実装
#include <cstdio> #include <algorithm> #include <vector> #include <functional> using namespace std; //gは隣接リスト //gを破壊する vector<int> EulerianTrail(const int s, vector<vector<int>> &g, const bool directed) { function<void (int, vector<int> &)> dfs = [&](int u, vector<int> &trail) { while (!g[u].empty()) { int v = g[u].back(); g[u].pop_back(); if (!directed) { for (int i = 0; i < g[v].size(); i ++) { if (g[v][i] == u) { g[v].erase(g[v].begin() + i); break; } } } dfs(v, trail); } trail.push_back(u); }; vector<int> trail; dfs(s, trail); reverse(trail.begin(), trail.end()); return trail; } int main() { int n, m; scanf("%d%d", &n, &m); vector<vector<int>> g(n); for (int i = 0; i < m; i ++) { int a, b; scanf("%d%d", &a, &b); a --, b --; g[a].push_back(b); g[b].push_back(a); } //次数が奇数の頂点を列挙し、適当につなぐ vector<int> odd; for (int i = 0; i < n; i ++) if (g[i].size() & 1) odd.push_back(i); int cnt = 0; for (int i = 0; i < odd.size(); i += 2) { int a = odd[i], b = odd[i + 1]; g[a].push_back(b); g[b].push_back(a); cnt ++; } //オイラー閉路を構築する auto trail = EulerianTrail(0, g, false); //オイラー路を順に辿り、向きを交互につけていく vector<pair<int, int>> ans; for (int i = 0; i < trail.size() - 1; i ++) { int a = trail[i], b = trail[i + 1]; if (i & 1) ans.emplace_back(a, b); else ans.emplace_back(b, a); } //すべての辺の数が奇数個のときは、頂点0に自己辺を張る if ((m + cnt) & 1) ans.emplace_back(0, 0); printf("%d\n", (int) ans.size()); for (int i = 0; i < ans.size(); i ++) { printf("%d %d\n", ans[i].first + 1, ans[i].second + 1); } return 0; }