ขอบต่ำสุดที่ต้องเพิ่มเพื่อสร้าง Euler Circuit ใน C++

แนวคิด

กำหนดกราฟไม่มีทิศทาง b โหนด a ขอบ หาจำนวนขอบน้อยที่สุดที่ต้องเพิ่มเพื่อให้มี Euler Circuit (วงจรที่ผ่านทุกขอบ 1 ครั้ง)

เงื่อนไข Euler Circuit: ทุกโหนดต้องมี degree เป็นเลขคู่

วิธีการแก้ปัญหา

2 กรณี:

1. กราฟเป็น 1 connected component

• ถ้าทุกโหนด degree คู่ → มี Euler Circuit แล้ว (เพิ่ม 0 ขอบ)
• ถ้ามีโหนด degree คี่ (ต้องเป็นจำนวนคู่) → จับคู่โหนดคี่แบบสุ่ม เพิ่มขอบระหว่างคู่ → ทุกโหนดกลายเป็นคู่

2. กราฟมีหลาย connected components

• แบ่ง component เป็น Odd (มีโหนดคี่ ≥1) และ Even (โหนดคู่ทั้งหมด)
• Even components: เลือกโหนดตัวแทนจัดเรียงเป็นเส้น เพิ่มขอบเชื่อมติดกัน → กลายเป็น 1 Odd component
• Odd components: วางแบบ cyclic เลือกโหนดคี่ 2 ตัวจากแต่ละ component เชื่อมกับ component ติดกัน → กลายเป็น 1 connected component
• จากนั้นจัดการตามกรณี 1

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

void dfs1(vector<int> g1[], int vis1[], int odd1[], int deg1[], int comp, int v){ ... }

int minEdge1(int n, int m, int s1[], int d1[]){
    vector<int> g1[n+1], e1, o1;
    int deg1[n+1], vis1[n+1], 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]]++;
    }
    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