หาจำนวนขอบน้อยที่สุดที่ต้องเพิ่มเพื่อสร้าง Euler Circuit ในกราฟไม่มีทิศทาง Python

Euler Circuit และการเพิ่มขอบน้อยที่สุด

Euler Circuit คือเส้นทางที่ผ่านทุกขอบของกราฟทีละขอบ และกลับมายังจุดเริ่มต้น กราฟไม่มีทิศทางมี Euler Circuit ได้ก็ต่อเมื่อ:

1. กราฟเชื่อมต่อ (Connected)
2. ทุกโหนดมีดีกรีเป็นเลขคู่

โจทย์: หาจำนวนขอบขั้นต่ำที่ต้องเพิ่มเพื่อให้กราฟมี Euler Circuit

แนวคิดการแก้ปัญหา

1. หา Connected Components ด้วย DFS
2. นับจำนวนโหนดที่มีดีกรีคี่ (odd_vert) ในแต่ละ Component
3. จัดกลุ่ม Component:
   • e: Component ที่ไม่มีโหนดคี่ (Eulerian)
   • o: Component ที่มีโหนดคี่ (Non-Eulerian)
4. คำนวณขอบที่ต้องเพิ่ม:
   • ถ้า o ว่าง และ e มี 1 Component → ต้องการ 0 ขอบ (มี Euler Circuit แล้ว)
   • ถ้า o ว่าง (หลาย Component Eulerian) → ต้องเพิ่ม len(e) ขอบเพื่อเชื่อม Component
   • ถ้ามี Component Non-Eulerian: ต้องเพิ่ม len(e) ขอบเชื่อม Component Eulerian + sum(odd_vert[i]//2) ขอบแก้โหนดคี่ในแต่ละ Component Non-Eulerian

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

def dfs(g, visit, odd_vert, degree, comp, v):
    visit[v] = 1
    if degree[v] % 2 == 1:
        odd_vert[comp] += 1
    for u in g[v]:
        if visit[u] == 0:
            dfs(g, visit, odd_vert, degree, comp, u)

def solve(n, m, s, d):
    g = [[] for _ in range(n + 1)]
    e = []  # Eulerian components
    o = []  # Non-Eulerian components
    degree = [0] * (n + 1)
    visit = [0] * (n + 1)
    odd_vert = [0] * (n + 1)
    
    for i in range(m):
        g[s[i]].append(d[i])
        g[d[i]].append(s[i])
        degree[s[i]] += 1
        degree[d[i]] += 1
    
    ans = 0
    comp = 0
    for i in range(1, n + 1):
        if visit[i] == 0:
            comp += 1
            dfs(g, visit, odd_vert, degree, comp, i)
            if odd_vert[comp] == 0:
                e.append(comp)
            else:
                o.append(comp)
    
    if len(o) == 0 and len(e) == 1:
        return 0
    if len(o) == 0:
        return len(e)
    if len(e) != 0:
        ans += len(e)
    for i in range(len(o)):
        ans += odd_vert[o[i]] // 2
    return ans

# ตัวอย่าง: 3 โหนด, 2 ขอบ (1-2, 2-3)
b = 3
a = 2
source = [1, 2]
destination = [2, 3]
print(solve(b, a, source, destination))  # 1