पायथन में यूलर सर्किट बनाने के लिए जोड़ने के लिए आवश्यक न्यूनतम किनारे

मान लीजिए कि हमारे पास बी संख्या के नोड्स और कई किनारों का एक अप्रत्यक्ष ग्राफ है; हमें इस ग्राफ में यूलर सर्किट बनाने के लिए आवश्यक न्यूनतम किनारों को खोजना होगा।

तो, अगर इनपुट पसंद है

तो आउटपुट 1 होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

एक फ़ंक्शन को परिभाषित करें dfs() । इसमें g, विज़िट, विषम_वर्ट, डिग्री, COMP, v
विज़िट[v] :=1
यदि डिग्री [v] mod 2 1 के समान है, तो
- odd_vert[comp]:=odd_vert[comp] + 1
आपके लिए 0 से g के आकार के बीच[v], करें
- यदि विज़िट[u] 0 के समान है, तो
  - dfs(g, विज़िट, ऑड_वर्ट, डिग्री, COMP, यू)
मुख्य विधि से निम्न कार्य करें -
g :=n+1 रिक्त सूचियों की सूची
e :=एक नई सूची
:=एक नई सूची
डिग्री:=आकार की नई सूची (n + 1) और 0 से भरें
विजिट करें :=आकार की नई सूची (n + 1) और 0 से भरें
odd_vert :=आकार की नई सूची (n + 1) और भरें
0 के साथ
0 से मी की सीमा में i के लिए, करें
- g[s[i]] के अंत में d[i] डालें,
- g के अंत में s[i] डालें[d[i]]
- डिग्री[s[i]] :=Degree[s[i]] + 1
- डिग्री[d[i]] :=डिग्री[d[i]] + 1
उत्तर:=0, COMP:=0
i के लिए 1 से n + 1 की श्रेणी में, करें
- यदि विज़िट[i] 0 के समान है, तो
  - comp :=COMP + 1
  - dfs(g, विज़िट, ऑड_वर्ट, डिग्री, COMP, i)
  - यदि विषम_वर्ट[comp] 0 के समान है, तो
    - ई के अंत में COMP डालें
  - अन्यथा,
    - ओ के अंत में COMP डालें
यदि o का आकार 0 के समान है और e का आकार 1 के समान है, तो
- वापसी 0
यदि o का आकार 0 के समान है, तो
- ई का वापसी आकार
यदि e का आकार 0 के समान नहीं है, तो
- उत्तर:=उत्तर + ई का आकार
i के लिए 0 से o के आकार की सीमा में, करते हैं
- उत्तर:=उत्तर + विषम_वर्ट[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]