Pythonでオイラー回路を作成するために追加する必要のある最小エッジ

b個のノードと数個のエッジの無向グラフがあるとします。このグラフでオイラー回路を構築するために必要な最小エッジを見つける必要があります。

したがって、入力が次のような場合

その場合、出力は1になります。

これを解決するには、次の手順に従います-

• 関数dfs（）を定義します。これには、g、visit、odd_vert、degree、comp、vが必要です
• visit [v]：=1
• 次数[v]mod2が1と同じ場合、
  • odd_vert [comp]：=odd_vert [comp] + 1
• 範囲0からg[v]のサイズのuの場合、実行
  • visit [u]が0と同じ場合、
    • dfs（g、visit、odd_vert、degree、comp、u）
• メインの方法から次のようにします-
• g：=n+1個の空白リストのリスト
• e：=新しいリスト
• ：=新しいリスト
• degree：=サイズの新しいリスト（n + 1）と0で埋める
• ：=サイズの新しいリスト（n + 1）にアクセスし、0を入力します
• odd_vert：=サイズ（n + 1）と塗りつぶしの新しいリスト
• 0で
• 0からmの範囲のiについては、
  • g [s [i]]
  の最後にd[i]を挿入します
  • g [d [i]]
  の最後にs[i]を挿入します
  • 度[s[i]]：=度[s [i]] + 1
  • 度[d[i]]：=度[d [i]] + 1
• ans：=0、comp：=0
• 1からn+1の範囲のiについては、
  • visit [i]が0と同じ場合、
    • comp：=comp + 1
    • dfs（g、visit、odd_vert、degree、comp、i）
    • odd_vert [comp]が0と同じ場合、
      • eの最後にcompを挿入
    • それ以外の場合、
      • oの最後にcompを挿入
• oのサイズが0と同じで、eのサイズが1と同じ場合、
  • 0を返す
• oのサイズが0と同じ場合、
  • eのサイズを返す
• eのサイズが0と同じでない場合、
  • ans：=ans+eのサイズ
• 0からoのサイズの範囲のiについては、
  • 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