C++로 오일러 회로 완성하기: 추가해야 할 최소 간선 수 구하는 방법

개념

b개의 노드와 a개의 간선으로 이루어진 무방향 그래프가 주어졌을 때, 해당 그래프에서 오일러 회로(Euler Circuit)를 완성하기 위해 추가해야 하는 최소 간선의 개수를 구하는 것이 이 글의 목표입니다.

입력

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

출력

1

노드 1과 3을 연결하는 간선 하나를 추가하면 오일러 회로가 완성됩니다.

접근 방법

그래프에 오일러 회로가 존재하려면 모든 노드의 차수(degree)가 반드시 짝수여야 합니다. 그래야 어떤 노드에 진입한 뒤 다시 빠져나갈 수 있는 간선이 항상 존재하기 때문입니다.

이 문제는 크게 두 가지 경우로 나누어 생각할 수 있습니다.

그래프가 하나의 연결 요소(Connected Component)로 이루어진 경우

이 경우 그래프의 모든 노드가 짝수 차수를 가지고 있다면 이미 오일러 회로가 존재하므로 간선을 추가할 필요가 없습니다. 반면 홀수 차수를 가진 노드가 하나라도 있다면 간선을 추가해야 합니다.

흥미로운 점은 그래프에 홀수 차수 정점이 항상 짝수 개 존재한다는 사실입니다. 이는 전체 차수의 합이 항상 짝수라는 성질(모든 간선이 양쪽 끝 정점의 차수에 각각 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는 연결 요소 번호입니다
    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);
        }
    }
    // 그래프 전체가 하나의 연결 요소이면서
    // 모든 차수가 짝수인 경우
    if (o1.size() == 0 && e1.size() == 1)
        return 0;
    // 모든 연결 요소가 짝수형인 경우
    if (o1.size() == 0)
        return e1.size();
    // 짝수 연결 요소가 하나 이상 존재하는 경우
    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