C++でオイラー回路を構築するために追加すべき最小エッジ数

概要

ノード数 b、エッジ数 a の無向グラフが与えられたとき、そのグラフにオイラー回路（Euler Circuit）を構築するために追加すべき最小のエッジ数を求めるのが本記事のテーマです。

入力例

b = 3,
a = 2
Edges[] = {{1, 2}, {2, 3}}

出力例

1

ノード1とノード3をつなぐことで、オイラー回路を構築できます。

考え方

グラフにオイラー回路が存在するためには、すべてのノードの次数が偶数である必要があります。次数が偶数であれば、あるノードに入った後、別のエッジを使って出ていくことができるためです。

ここで、次の2つの場合が考えられます。

ケース1：グラフが1つの連結成分のみを持つ場合

この場合、グラフ内のすべてのノードの次数が偶数であれば、グラフはすでにオイラー回路を持っているため、エッジを追加する必要はありません。一方、奇数次のノードが存在する場合は、エッジを追加する必要があります。

重要な性質として、奇数次の頂点は必ず偶数個存在します。これは「偶数次ノードの次数の合計」と「奇数次ノードの次数の合計」を足した値が総次数であり、各エッジがこの合計に2ずつ寄与するため、総次数は必ず偶数になるという事実から容易に確認できます。

したがって、グラフ内の奇数次ノード同士をペアにし、その間にエッジを追加していけば、すべてのノードの次数を偶数にでき、オイラー回路が存在するようになります。

ケース2：グラフが複数の非連結成分を持つ場合

まず、各連結成分を「奇成分」と「偶成分」に分類します。奇成分とは、少なくとも1つの奇数次ノードを含む成分のことです。

次に、すべての偶成分からそれぞれ任意の頂点を1つ選び、それらを一列に並べます。隣接する頂点同士の間にエッジを追加することで、偶成分同士を連結し、2つの奇数次ノードを持つ1つの奇成分へと変換できます。

さらに、奇成分どうしをつなぐ場合は、非連結成分の数と同じ数のエッジですべての奇成分を連結できます。具体的には、成分を環状に並べ、各成分から2つの奇数次ノードを選び、左右両隣の成分と接続します。こうして得られるのは単一の連結成分なので、あとはケース1と同じ手順で処理すればよいことになります。

実装例

// このC++プログラムは、オイラー回路を作成するために
// 必要な最小エッジ数を求めます
#include <bits/stdc++.h>
using namespace std;
// 深さ優先探索（DFS）により連結成分を調べる
void dfs1(vector<int> g1[], int vis1[], int odd1[],
int deg1[], int comp, int v){
    vis1[v] = 1;
    if (deg1[v]%2 == 1)
        odd1[comp]++;
    for (int u : g1[v])
        if (vis1[u] == 0)
            dfs1(g1, vis1, odd1, deg1, comp, u);
}
// オイラー回路の構築に必要な最小エッジ数を返す
int minEdge1(int n, int m, int s1[], int d1[]){
    // g1 : グラフの隣接リスト表現を格納
    // e1 : 偶数次頂点リスト
    // o1 : 奇数次頂点リスト
    vector<int> g1[n+1], e1, o1;
    int deg1[n+1]; // 各頂点の次数
    int vis1[n+1]; // DFSでの訪問状態
    int odd1[n+1]; // 各連結成分内の奇数次ノード数
    memset(deg1, 0, sizeof(deg1));
    memset(vis1, 0, sizeof(vis1));
    memset(odd1, 0, sizeof(odd1));
    for (int i = 0; i < m; i++){
        g1[s1[i]].push_back(d1[i]);
        g1[d1[i]].push_back(s1[i]);
        deg1[s1[i]]++;
        deg1[d1[i]]++;
    }
    // ans は結果、comp は連結成分ID
    int ans = 0, comp = 0;
    for (int i = 1; i <= n; i++){
        if (vis1[i]==0){
            comp++;
            dfs1(g1, vis1, odd1, deg1, comp, i);
            // 連結成分が偶成分かどうかを判定
            if (odd1[comp] == 0)
                e1.push_back(comp);
            // 連結成分が奇成分かどうかを判定
            else
                o1.push_back(comp);
        }
    }
    // グラフ全体が1つの偶数次の連結成分である場合
    if (o1.size() == 0 && e1.size() == 1)
        return 0;
    // すべての連結成分が偶成分である場合
    if (o1.size() == 0)
        return e1.size();
    // 少なくとも1つの偶成分が存在する場合
    if (e1.size() != 0)
        ans += e1.size();
    // すべての奇成分について処理
    for (int i : o1)
        ans += odd1[i]/2;
    return ans;
}
// メイン関数
int main(){
    int b = 3, a = 2;
    int source1[] = { 1, 2 };
    int destination1[] = { 2, 3 };
    cout << minEdge1(b, a, source1, destination1) << endl;
    return 0;
}

出力

1