ขอบขั้นต่ำที่จำเป็นในการเพิ่มเพื่อสร้างออยเลอร์วงจรใน Python

สมมติว่าเรามีกราฟที่ไม่มีทิศทางของจำนวนโหนด b และจำนวนขอบ เราต้องหาขอบขั้นต่ำที่จำเป็นในการสร้างวงจรออยเลอร์ในกราฟนี้

ดังนั้นหากอินพุตเป็นแบบ

แล้วผลลัพธ์จะเป็น 1

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน dfs() จะใช้เวลา g, visit, odd_vert, degree, comp, v
• เยี่ยมชม[v] :=1
• ถ้าดีกรี[v] mod 2 เหมือนกับ 1 แล้ว
  • odd_vert[comp] :=odd_vert[comp] + 1
• สำหรับคุณในช่วง 0 ถึงขนาด g[v] ทำ
  • ถ้า visit[u] เท่ากับ 0 แล้ว
    • dfs(g, visit, odd_vert, degree, comp, u)
• จากวิธีหลัก ให้ทำดังนี้ -
• g :=รายการของรายการว่าง n+1
• e :=รายการใหม่
• :=รายการใหม่
• degree :=รายการขนาดใหม่ (n + 1) และเติมด้วย 0
• visit :=รายการขนาดใหม่ (n + 1) และเติม 0
• odd_vert :=รายการขนาดใหม่ (n + 1) และเติม
• มี 0
• สำหรับฉันในช่วง 0 ถึง m ให้ทำ
  • ใส่ d[i] ที่ส่วนท้ายของ g[s[i]]
  • แทรก s[i] ที่ส่วนท้ายของ g[d[i]]
  • ดีกรี[s[i]] :=องศา[s[i]] + 1
  • องศา[d[i]] :=องศา[d[i]] + 1
• แทน :=0, คอมพ์ :=0
• สำหรับฉันในช่วง 1 ถึง n + 1 ทำ
  • ถ้า visit[i] เท่ากับ 0 แล้ว
    • คอมพ์ :=คอมพ์ + 1
    • dfs(g, visit, odd_vert, degree, comp, i)
    • ถ้า odd_vert[comp] เหมือนกับ 0 แล้ว
      • แทรก comp ที่ส่วนท้ายของ e
    • มิฉะนั้น
      • แทรก comp ที่ส่วนท้ายของ o
• ถ้าขนาดของ o เท่ากับ 0 และขนาดของ e เท่ากับ 1 ดังนั้น
  • คืน 0
• ถ้าขนาด o เท่ากับ 0 แล้ว
  • ขนาดผลตอบแทนของ e
• ถ้าขนาดของ e ไม่เท่ากับ 0 แล้ว
  • ans :=ans + ขนาดของ e
• สำหรับ i ในช่วง 0 ถึงขนาด o ทำ
  • ans :=ans + odd_vert[i] / 2 (ใช้เฉพาะส่วนจำนวนเต็ม)
• คืนสินค้า

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

def dfs(g, visit, odd_vert, degree, comp, v):
   visit[v] = 1
   if (degree[v] % 2 == 1):
      odd_vert[comp] += 1
   for u in range(len(g[v])):
      if (visit[u] == 0):
         dfs(g, visit, odd_vert, degree, comp, u)
def solve(n, m, s, d):
   g = [[] for i 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))

อินพุต

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

ผลลัพธ์

1