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

Khái niệm

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

Ví dụ: b=3, a=2, cạnh {{1,2},{2,3}} → thêm 1 cạnh (1-3) để có chu trình Euler.

Phương pháp

Điều kiện Euler Circuit: mọi đỉnh đều bậc chẵn.

• Một thành phần liên thông: nếu đã toàn bậc chẵn → 0. Nếu có đỉnh bậc lẻ (luôn số chẵn), ghép cặp các đỉnh bậc lẻ tùy ý, thêm cạnh nối → số cạnh = (số đỉnh bậc lẻ)/2.
• Nhiều thành phần liên thông:
  • Phân loại thành phần: "lẻ" (có đỉnh bậc lẻ), "chẵn" (toàn bậc chẵn).
  • Nối các thành phần chẵn thành chuỗi → tạo thành một thành phần lẻ mới (2 đỉnh bậc lẻ). Số cạnh = số thành phần chẵn.
  • Nối các thành phần lẻ thành vòng tròn: mỗi thành phần lẻ chọn 2 đỉnh bậc lẻ nối với hai bên → số cạnh = số thành phần lẻ.
  • Tổng cộng = số thành phần chẵn + tổng(odd_degree_in_component/2).

Ví dụ (C++)

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

void dfs1(vector<int> g1[], int vis1[], int odd1[], int deg1[], int comp, int v){
    vis1[v]=1; if(deg1[v]%2) odd1[comp]++;
    for(int u:g1[v]) if(!vis1[u]) dfs1(g1,vis1,odd1,deg1,comp,u);
}

int minEdge1(int n, int m, int s1[], int d1[]){
    vector<int> g1[n+1], e1, o1;
    int deg1[n+1]={0}, vis1[n+1]={0}, odd1[n+1]={0};
    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]){
        comp++; dfs1(g1,vis1,odd1,deg1,comp,i);
        if(odd1[comp]==0) e1.push_back(comp);
        else o1.push_back(comp);
    }
    if(o1.empty() && e1.size()==1) return 0;
    if(o1.empty()) return e1.size();
    if(!e1.empty()) ans+=e1.size();
    for(int i:o1) ans+=odd1[i]/2;
    return ans;
}

int main(){
    int b=3, a=2;
    int source1[]={1,2}, destination1[]={2,3};
    cout<<minEdge1(b,a,source1,destination1)<<endl;
    return 0;
}

Đầu ra

1