Python中構建歐拉回路所需的最少邊數

假設我們有一個具有b個節點和一定數量邊的無向圖；我們必須找到構建歐拉回路所需的最小邊數。

因此，如果輸入如下所示：

那麼輸出將是1。

為了解決這個問題，我們將遵循以下步驟：

  • 定義一個函式dfs()。它將接收g、visit、odd_vert、degree、comp、v。
  • visit[v] := 1
  • 如果degree[v] mod 2等於1，則
    • odd_vert[comp] := odd_vert[comp] + 1
  • 對於u in range 0 to size of g[v]，執行：
    • 如果visit[u]等於0，則
      • dfs(g, visit, odd_vert, degree, comp, u)
  • 在主方法中執行以下操作：
  • g := 一個包含n+1個空列表的列表
  • e := 一個新列表
  • o := 一個新列表
  • degree := 一個大小為(n + 1)並填充為0的新列表
  • visit := 一個大小為(n + 1)並填充為0的新列表
  • odd_vert := 一個大小為(n + 1)並填充
  • 為0的新列表
  • 對於i in range 0 to m，執行：
    • 將d[i]插入g[s[i]]的末尾
    • 將s[i]插入g[d[i]]的末尾
    • degree[s[i]] := degree[s[i]] + 1
    • degree[d[i]] := degree[d[i]] + 1
  • ans := 0, comp := 0
  • 對於i in range 1 to n + 1，執行：
    • 如果visit[i]等於0，則
      • comp := comp + 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 in range 0 to o的大小，執行：
    • ans := ans + odd_vert[i] / 2（只取整數部分）
  • 返回ans

示例

讓我們來看下面的實現，以便更好地理解：

 線上演示

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

更新於：2020年8月27日

97 次檢視

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告