Số cạnh tối thiểu cần thêm để tạo chu trình Euler trong Python

Cho một đồ thị vô hướng với b nút và a cạnh. Ta cần tìm số cạnh tối thiểu cần thêm để đồ thị có chu trình Euler (Euler Circuit).

Ví dụ, với đồ thị như hình dưới đây:

Kết quả sẽ là 1.

Thuật toán giải quyết

• Hàm dfs(g, visit, odd_vert, degree, comp, v):
  • Đánh dấu visit[v] := 1.
  • Nếu degree[v] % 2 == 1 thì odd_vert[comp] += 1.
  • Duyệt các đỉnh kề u của v: nếu visit[u] == 0 thì gọi đệ quy dfs.
• Từ hàm chính:
  • Khởi tạo danh sách kề g, mảng degree, visit, odd_vert.
  • Đọc các cạnh, cập nhật g và degree.
  • Khởi tạo ans := 0, comp := 0, danh sách e (thành phần liên thông có đỉnh chẵn), o (thành phần liên thông có đỉnh lẻ).
  • Duyệt các đỉnh 1..n: nếu chưa thăm thì tăng comp, gọi dfs. Phân loại thành e hoặc o dựa trên odd_vert[comp].
  • Nếu len(o) == 0 và len(e) == 1: trả về 0.
  • Nếu len(o) == 0: trả về len(e).
  • Nếu len(e) != 0: ans += len(e).
  • Với mỗi thành phần trong o: ans += odd_vert[i] // 2.
  • Trả về ans.

Ví dụ minh họa

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 = []
    o = []
    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[i] // 2
    return ans

b = 3
a = 2
source = [1, 2]
destination = [2, 3]
print(solve(b, a, source, destination))  # 1

Đầu vào

b = 3, a = 2, source = [1, 2], destination = [2, 3]

Đầu ra

1