これは 帰ってきた AOJ-ICPC Advent Calendar 2022 の9日目です。
問題概要
$N$ 頂点 $ M $ 辺の無向グラフが与えられる。このグラフに、多重辺が含まないように辺を自由に追加した時、一筆書き可能にすることができるか判定せよ。可能ならば構築方法の1つを、不可能ならば-1を出力する。
制約
$3 \leq N \leq N$
$0 \leq M \leq N(N-1)/2$
入力で与えられるグラフは多重辺を含まない
解法
題意を満たすようなグラフについて有名な定理が存在します。詳しくは次のリンクで。
オイラーグラフの定理（一筆書きできる条件）とその証明 | 高校数学の美しい物語
結局、「全ての頂点の次数が偶数」かつ「グラフ全体が連結」を満たすような辺の追加の仕方を求める問題ということになります。
まず簡単のため、「全ての頂点の次数が偶数」が満たされている入力に対して、「グラフ全体が連結」の条件を満たす方法について考察してみることにします。
- 連結成分の数が1つの場合
そのまま元の問題の条件を満たしています。
- 連結成分の数が3つ以上の場合
それぞれの連結成分から要素を1つずつ選び出し、それらを輪のように繋ぐことで、次数の条件を変えることなく全体を連結にすることが可能です。
- 連結成分の数が2つの場合
ここでは更に細かい場合分けが生じます。
連結成分の大きさが共に2以上の場合は簡単で、それぞれから代表で2要素ずつ選び出し、完全二部グラフのように辺を追加すると、条件を満たすことが出来ます。
次に、そうでない場合、つまり片方が孤立点である場合を考えます。孤立点ではない方の連結成分内で、まだ結ばれていない2頂点があるならば、その2頂点と孤立点の3点を結ぶことで、条件を満たすようになります。
そのような2頂点が選べない場合、その連結成分は完全グラフであり、この場合のみ構築が不可能ということが分かります。
「グラフ全体が連結」の条件の考察が終わったので、「全ての頂点の次数が偶数」の条件について考えます。
孤立点の扱いが厄介そうということが分かったので、先に処理することにします。
奇数次数の頂点の個数はグラフ全体で偶数個あり(グラフの次数の総和は偶数なので)、奇数次数の頂点2個と孤立点をペアにすることを繰り返します。この結果、孤立点が先に無くなるか、奇数次数の頂点が先に無くなるかの2択になります。
孤立点が無くなった場合、連結にするパートで困ることはないので、次数だけ合わせれば良いことになります。奇数次数の頂点が無くなった場合、上の場合に帰着するので、連結パートを同様に行えばよいです。
ここ書いてる時に、$N = 4, M = 1$ で落とせることに気が付きました…
逆にこのケース以外は落ちないと思うので、場合分けで回避するか、別の方法で対処することにします。僕は(奇数次数)-(孤立点)-(孤立点)-(孤立点)-…のように繋ぎました。
(そもそも孤立点を先に処理してるのがナンセンスかもしれない)
追記(2022/12/11修正)
この孤立点の処理の仕方について、正当性を示してなかったので追記します。
そもそも奇数次数の頂点が存在しない場合は上で解いた場合に帰着するので、ここでは考えなくてよいです。
逆に奇数頂点が存在するならば、上の構築方法で孤立点を全て消化することが出来ます。この時、全ての次数を偶数にする方法が存在するならば、この構築は正当です。
まず追加した孤立点の末尾(という表現が正しいのか分かりませんが…)の次数が奇数になっているので、他の適当な奇数次数と辺を結び、次数を偶数にします。この時グラフにまだ奇数次数の頂点が存在するならば、元々孤立点だった頂点を1つ代表として選び、それらの間に全て辺を追加すればよいです。これで次数は全て偶数になっており、元々孤立点だったことから、多重辺の条件にも違反しておらず正当です。
最後に連結性を無視して、次数の条件を合わせる方法について考察します。
先に結論を書くと、補グラフのDFS木を作成し、葉の次数を見て奇数ならばその辺を採用して、親の次数を変更し再帰的に解いていけば良いです。
補グラフのDFS木上の辺のみを使うとしてよい理由は、もし後退辺を使うような解が存在した場合、後対辺を除外し、その2点を結ぶDFS木上のパスの辺を使うかどうか反転させれば、それも解となるからです。
実装
#pragma GCC optimize ("Ofast") #include <bits/stdc++.h> using namespace std; typedef long long int ll; struct UnionFind{ vector<int> par,num; UnionFind(int n):par(n),num(n,1){ iota(par.begin(),par.end(),0); //include<numeric> } int find(int v){ return (par[v]==v)?v:(par[v]=find(par[v])); } void unite(int u, int v){ u = find(u),v = find(v); if(u == v) return; if(num[u] < num[v]) swap(u,v); num[u] += num[v]; par[v] = u; } bool same(int u, int v){ return find(u) == find(v); } int size(int v){ return num[find(v)]; } }; int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n,m; cin >> n >> m; vector<vector<bool>> g(n,vector<bool>(n)); vector<int> deg(n); UnionFind uf(n); for (int i = 0; i < n; ++i) { g[i][i] = true; } for (int i = 0; i < m; ++i) { int x,y; cin >> x >> y; x--; y--; g[x][y] = g[y][x] = true; uf.unite(x, y); deg[x]++; deg[y]++; } vector<pair<int,int>> res; auto add = [&](int s,int t)->void{ res.push_back({s, t}); g[s][t] = g[t][s] = true; deg[s]++; deg[t]++; uf.unite(s, t); }; // 孤立点を貪欲に処理 { vector<int> one; vector<int> odd; for (int i = 0; i < n; ++i) { if(deg[i] == 0) one.push_back(i); if(deg[i] % 2 == 1) odd.push_back(i); } if(odd.size()){ int s = odd.back(); while(one.size()){ int t = one.back(); one.pop_back(); add(s, t); s = t; } } } vector<bool> used(n); // 次数の条件を揃える // 補グラフのdfs tree auto dfs = [&](auto dfs,int s,int p)->void{ for (int i = 0; i < n; ++i) { if(g[s][i] or used[i]) continue; used[i] = true; dfs(dfs, i, s); } if(deg[s]%2 == 1){ if(p == -1){ cout << -1 << "\n"; exit(0); } add(s, p); } }; for (int i = 0; i < n; ++i) { if(used[i]) continue; used[i] = true; dfs(dfs, i, -1); } // 連結にする vector<pair<int,int>> v; for (int i = 0; i < n; ++i) { if(uf.find(i) == i){ int j = -1; for (int k = 0; k < n; ++k) { if(uf.same(i, k) and i != k){ j = k; break; } } v.push_back({i,j}); } } if(v.size() == 2){ if(v[1].second == -1) swap(v[0], v[1]); if(v[0].second != -1){ add(v[0].first, v[1].first); add(v[0].first, v[1].second); add(v[0].second, v[1].first); add(v[0].second, v[1].second); } else{ bool done = false; for (int i = 0; i < n; ++i) { if(done or i == v[0].first) continue; for (int j = 0; j < n; ++j) { if(done or j == v[0].first) continue; if(!g[i][j]){ done = true; add(i, j); add(i, v[0].first); add(j, v[0].first); } } } if(!done){ cout << -1 << "\n"; return 0; } } } else if(v.size() >= 3){ for (int i = 0; i < v.size(); ++i) { int j = i+1 < v.size() ? i+1 : 0; add(v[i].first, v[j].first); } } cout << res.size() << "\n"; for(auto p:res){ if(p.first > p.second) swap(p.first, p.second); cout << p.first+1 << " " << p.second+1 << "\n"; } }
